String Flashcards
- Is Subsequence
Easy
Given two strings s and t, return true if s is a subsequence of t, or false otherwise.
A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e., “ace” is a subsequence of “abcde” while “aec” is not).
Example 1:
Input: s = “abc”, t = “ahbgdc”
Output: true
Example 2:
Input: s = “axc”, t = “ahbgdc”
Output: false
class Solution {
public boolean isSubsequence(String s, String t) {
if(s.length()>t.length()){
return false; }
Queue<Character> q = new LinkedList<>();
for(int i =0;i<s.length();i++){
q.add(s.charAt(i));
}
for(int j = 0;j<t.length();j++){
if(!q.isEmpty()&& t.charAt(j)==q.peek()){
q.poll();
}
}</Character>
if(q.isEmpty()){
return true;
}
return false;
}
}
- Top K Frequent Words
Medium
Given an array of strings words and an integer k, return the k most frequent strings.
Return the answer sorted by the frequency from highest to lowest. Sort the words with the same frequency by their lexicographical order.
Example 1:
Input: words = [“i”,”love”,”leetcode”,”i”,”love”,”coding”], k = 2
Output: [“i”,”love”]
Explanation: “i” and “love” are the two most frequent words.
Note that “i” comes before “love” due to a lower alphabetical order.
Example 2:
Input: words = [“the”,”day”,”is”,”sunny”,”the”,”the”,”the”,”sunny”,”is”,”is”], k = 4
Output: [“the”,”is”,”sunny”,”day”]
Explanation: “the”, “is”, “sunny” and “day” are the four most frequent words, with the number of occurrence being 4, 3, 2 and 1 respectively.
class Solution {
public List<String> topKFrequent(String[] words, int k) {
Map<String, Integer> hm = new HashMap<>();
for(int i = 0;i<words.length;i++){
hm.put(words[i], hm.getOrDefault(words[i],0)+1);
}
List<String> list = new ArrayList<>(hm.keySet());
Collections.sort(list, new Comparator<String>(){
@Override
public int compare(String a, String b){
if(hm.get(a)==hm.get(b)){
return a.compareTo(b);
}
return hm.get(b)-hm.get(a);
}
});
List<String> output = new ArrayList<>();
for(int i =0;i<k;i++){
output.add(list.get(i));
}
return output;</String></String></String></String>
} }
- Minimum Remove to Make Valid Parentheses
Medium
Given a string s of ‘(‘ , ‘)’ and lowercase English characters.
Your task is to remove the minimum number of parentheses ( ‘(‘ or ‘)’, in any positions ) so that the resulting parentheses string is valid and return any valid string.
Formally, a parentheses string is valid if and only if:
It is the empty string, contains only lowercase characters, or
It can be written as AB (A concatenated with B), where A and B are valid strings, or
It can be written as (A), where A is a valid string.
Example 1:
Input: s = “lee(t(c)o)de)”
Output: “lee(t(c)o)de”
Explanation: “lee(t(co)de)” , “lee(t(c)ode)” would also be accepted.
Example 2:
Input: s = “a)b(c)d”
Output: “ab(c)d”
class Solution {
public String minRemoveToMakeValid(String s) {
int open=0 ;
int close=0;
StringBuilder sb = new StringBuilder();
for(int i =0;i<s.length();i++){
if(s.charAt(i)==’(‘){
open++;
sb.append(s.charAt(i));
}
else if(s.charAt(i)==’)’ ){
open–;
if(open<0){
open = 0;
continue;
}
sb.append(s.charAt(i));
}
else if(s.charAt(i)!=’)’ && s.charAt(i)!=’(‘){
sb.append(s.charAt(i));
}
}
for(int i =sb.length()-1;i>=0;i--){
if(open>0 && sb.charAt(i)=='('){
sb.deleteCharAt(i);
open--;
}
}
return sb.toString();
}
}
- Destination City
Easy
You are given the array paths, where paths[i] = [cityAi, cityBi] means there exists a direct path going from cityAi to cityBi. Return the destination city, that is, the city without any path outgoing to another city.
It is guaranteed that the graph of paths forms a line without any loop, therefore, there will be exactly one destination city.
Example 1:
Input: paths = [[“London”,”New York”],[“New York”,”Lima”],[“Lima”,”Sao Paulo”]]
Output: “Sao Paulo”
Explanation: Starting at “London” city you will reach “Sao Paulo” city which is the destination city. Your trip consist of: “London” -> “New York” -> “Lima” -> “Sao Paulo”.
Example 2:
Input: paths = [[“B”,”C”],[“D”,”B”],[“C”,”A”]]
Output: “A”
Explanation: All possible trips are:
“D” -> “B” -> “C” -> “A”.
“B” -> “C” -> “A”.
“C” -> “A”.
“A”.
Clearly the destination city is “A”.
class Solution {
public String destCity(List<List<String>> paths) {</String>
HashMap<String,Integer> hm = new HashMap<>();
for(int i=0;i<paths.size();i++){
String src=paths.get(i).get(0);
String dest = paths.get(i).get(1);
hm.put(src, hm.getOrDefault(src,0)+1);
if(!hm.containsKey(dest)){
hm.put(dest,0);
}
}
Set<String> set = hm.keySet();
for(String s : set){
if(hm.get(s)==0){
return s;
}
}
return "";
} }
- Number of Distinct Substrings in a String
Medium
Given a string s, return the number of distinct substrings of s.
A substring of a string is obtained by deleting any number of characters (possibly zero) from the front of the string and any number (possibly zero) from the back of the string.
Example 1:
Input: s = “aabbaba”
Output: 21
Explanation: The set of distinct strings is [“a”,”b”,”aa”,”bb”,”ab”,”ba”,”aab”,”abb”,”bab”,”bba”,”aba”,”aabb”,”abba”,”bbab”,”baba”,”aabba”,”abbab”,”bbaba”,”aabbab”,”abbaba”,”aabbaba”]
Example 2:
Input: s = “abcdefg”
Output: 28
class Solution {
public int countDistinct(String s) {
HashSet<String> set = new HashSet<>();
for(int i = 0; i < s.length(); i++){
int len = s.length() - i;
while(len > 0){
set.add(s.substring(i, i+len));
len--;
}
}
return set.size();
} }
- Add Strings
Easy
Given two non-negative integers, num1 and num2 represented as string, return the sum of num1 and num2 as a string.
You must solve the problem without using any built-in library for handling large integers (such as BigInteger). You must also not convert the inputs to integers directly.
Example 1:
Input: num1 = “11”, num2 = “123”
Output: “134”
Example 2:
Input: num1 = “456”, num2 = “77”
Output: “533”
Example 3:
Input: num1 = “0”, num2 = “0”
Output: “0”
class Solution {
int carry =0;
public String addStrings(String num1, String num2) {
int i = num1.length()-1;
int j = num2.length()-1;
StringBuilder sb = new StringBuilder();
while(i>=0 && j>=0){
int a = Character.getNumericValue(num1.charAt(i));
int b = Character.getNumericValue(num2.charAt(j));
int last = convert(a,b);
sb.append(last+””);
i–;
j–;
}
while(i>=0 ){
int a = Character.getNumericValue(num1.charAt(i));
int last = convert(a,0);
sb.append(last+"");
i--;
}
while(j>=0){
int b = Character.getNumericValue(num2.charAt(j));
int last = convert(0,b);
sb.append(last+"");
j--;
}
if(carry >0 )
sb.append(carry+"");
return sb.reverse().toString();
}
public int convert(int a, int b){
int sum = carry+a+b;
if(sum<9){
carry =0;
return sum;
} else{
int last = sum%10;
carry = sum/10;
return last;
}
} }
- Roman to Integer
Easy
13.2K
815
company
Amazon
company
Apple
company
Google
Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.
Symbol Value
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
For example, 2 is written as II in Roman numeral, just two ones added together. 12 is written as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II.
Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:
I can be placed before V (5) and X (10) to make 4 and 9.
X can be placed before L (50) and C (100) to make 40 and 90.
C can be placed before D (500) and M (1000) to make 400 and 900.
Given a roman numeral, convert it to an integer.
class Solution {
public int romanToInt(String s) {
HashMap<Character, Integer> hm = new HashMap<>();
hm.put(‘I’, 1);
hm.put(‘V’, 5);
hm.put(‘X’, 10);
hm.put(‘L’, 50);
hm.put(‘C’, 100);
hm.put(‘D’, 500);
hm.put(‘M’, 1000);
int sum = 0;
int index = 0;
while (index < s.length() - 1) {
if (hm.get(s.charAt(index)) < hm.get(s.charAt(index + 1))) {
sum = sum - hm.get(s.charAt(index));
} else if (hm.get(s.charAt(index)) >= hm.get(s.charAt(index + 1))) {
sum = sum + hm.get(s.charAt(index));
}
index++;
}
sum = sum + hm.get(s.charAt(index));
return sum;
}
}
- Longest Substring Without Repeating Characters
Solved
Medium
Topics
Companies
Given a string s, find the length of the longest
substring
without repeating characters.
Example 1:
Input: s = “abcabcbb”
Output: 3
Explanation: The answer is “abc”, with the length of 3.
Example 2:
Input: s = “bbbbb”
Output: 1
Explanation: The answer is “b”, with the length of 1.
Example 3:
Input: s = “pwwkew”
Output: 3
Explanation: The answer is “wke”, with the length of 3.
Notice that the answer must be a substring, “pwke” is a subsequence and not a substring.
class Solution {
public int lengthOfLongestSubstring(String s) {
char[] ch = s.toCharArray();
int maxCount = 0;
int count = 1;
for (int i = 0; i < ch.length; i++) {
Set<Character> hs = new HashSet<>();
count = 1;
hs.add(ch[i]);
for (int j = i + 1; j < ch.length; j++) {
if (!hs.contains(ch[j])) {
hs.add(ch[j]);
count++;
} else {
hs.clear();
break;
}
}
if (count > maxCount) {
maxCount = count;
}
}
return maxCount;
} }
- Search Suggestions System
Solved
Medium
You are given an array of strings products and a string searchWord.
Design a system that suggests at most three product names from products after each character of searchWord is typed. Suggested products should have common prefix with searchWord. If there are more than three products with a common prefix return the three lexicographically minimums products.
Return a list of lists of the suggested products after each character of searchWord is typed.
Example 1:
Input: products = [“mobile”,”mouse”,”moneypot”,”monitor”,”mousepad”], searchWord = “mouse”
Output: [[“mobile”,”moneypot”,”monitor”],[“mobile”,”moneypot”,”monitor”],[“mouse”,”mousepad”],[“mouse”,”mousepad”],[“mouse”,”mousepad”]]
Explanation: products sorted lexicographically = [“mobile”,”moneypot”,”monitor”,”mouse”,”mousepad”].
After typing m and mo all products match and we show user [“mobile”,”moneypot”,”monitor”].
After typing mou, mous and mouse the system suggests [“mouse”,”mousepad”].
class Solution {
public List<List<String>> suggestedProducts(String[] products, String searchWord) {
List<List<String>> output = new ArrayList<>();
for (int i = 0; i < searchWord.length(); i++) {
PriorityQueue<String> pq = new PriorityQueue<>();
String s = searchWord.substring(0, i + 1);
for (int j = 0; j < products.length; j++) {
String currString = products[j];</String></String></String>
if (currString.startsWith(s)) {
pq.add(currString);
}
}
List<String> res = new ArrayList<>();
int count = 0;
while(!pq.isEmpty() && count<3){
res.add(pq.poll());
count++;
}
output.add(res);
}
return output;
} }
- Length of Last Word
Solved
Easy
Topics
Companies
Given a string s consisting of words and spaces, return the length of the last word in the string.
A word is a maximal
substring
consisting of non-space characters only.
Example 1:
Input: s = “Hello World”
Output: 5
Explanation: The last word is “World” with length 5.
Example 2:
Input: s = “ fly me to the moon “
Output: 4
Explanation: The last word is “moon” with length 4.
class Solution {
public int lengthOfLastWord(String s) {
if(s.length()==0){
return 0;
}
String newString = s.trim().replaceAll("\\s+", " ");
String[] strArr = newString.split(" ");
String strLast = strArr[strArr.length - 1];
return strLast.length();
} }
