String
744. Find Smallest Letter Greater Than Target
public int firstUniqChar(String s) {
int[] count = new int[26];
int[] firstIndices = new int[26];
Arrays.fill(firstIndices, - 1);
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
count[c - 'a']++;
if (firstIndices[c - 'a'] == -1) {
firstIndices[c - 'a'] = i;
}
}
int res = Integer.MAX_VALUE;
for (char c = 'a'; c <= 'z'; c++) {
if (firstIndices[c - 'a'] != -1 && count[c - 'a'] == 1) {
res = Math.min(res, firstIndices[c - 'a']);
}
}
return res == Integer.MAX_VALUE ? -1 : res;
}Use a HashMap to record the order, verify the order and length.
public boolean isAlienSorted(String[] words, String order) {
Map<Character, Integer> map = new HashMap<>();
for (int i = 0; i < order.length(); i++) {
map.put(order.charAt(i), i);
}
for (int i = 0; i < words.length - 1; i++) {
String a = words[i];
String b = words[i + 1];
if (!valid(a, b, map)) {
return false;
}
}
return true;
}
private boolean valid(String a, String b, Map<Character, Integer> map) {
for (int i = 0; i < Math.min(a.length(), b.length()); i++) {
if (a.charAt(i) != b.charAt(i)) {
return map.get(a.charAt(i)) < map.get(b.charAt(i));
}
}
return a.length() <= b.length();
} Add string from right to left, if there one string is out of digits, count as zero.
public String addStrings(String num1, String num2) {
int i = num1.length() - 1, j = num2.length() - 1;
int carry = 0;
StringBuilder sb = new StringBuilder();
while (i >= 0 || j >= 0) {
int a = i >= 0 ? num1.charAt(i) - '0' : 0;
int b = j >= 0 ? num2.charAt(j) - '0' : 0;
int sum = a + b + carry;
carry = sum / 10;
sb.append(sum % 10);
i--;
j--;
}
if (carry == 1) sb.append(1);
return sb.reverse().toString();
} def addStrings(self, num1, num2):
res, i, j, s = [], len(num1)-1, len(num2)-1, 0
while i >=0 or j >= 0 or s:
if i >= 0:
s += int(num1[i])
i -= 1
if j >= 0:
s += int(num2[j])
j -= 1
res.append(str(s % 10))
s /= 10
res_str = ''.join(res[::-1])
return res_strUse StringBuilder to build characters when it is a letter. When encounter non-letter, build string and detect if it is not in banned and is the most common word.
T: O(n) S: O(n)
public String mostCommonWord(String paragraph, String[] banned) {
paragraph = paragraph + ".";
Set<String> ban = new HashSet<>();
for (String b : banned) ban.add(b);
Map<String, Integer> count = new HashMap<>();
int max = 0;
String res = "";
StringBuilder sb = new StringBuilder();
for (char c : paragraph.toCharArray()) {
if (Character.isLetter(c)) {
sb.append(Character.toLowerCase(c));
} else if (sb.length() > 0) {
String s = sb.toString();
if (!ban.contains(s)) {
count.put(s, count.getOrDefault(s, 0) + 1);
if (count.get(s) > max) {
res = s;
max = count.get(s);
}
}
sb = new StringBuilder();
}
}
return res;
}Convert each String to a map, get min count of all characters between 'a' and 'z'. Add the character to result.
public List<String> commonChars(String[] A) {
List<String> res = new ArrayList<>();
List<int[]> list = new ArrayList<>();
for (String s : A) {
int[] map = new int[26];
for (char c : s.toCharArray()) {
map[c - 'a']++;
}
list.add(map);
}
for (char c = 'a'; c <= 'z'; c++) {
int min = Integer.MAX_VALUE;
for (int i = 0; i < list.size(); i++) {
min = Math.min(min, list.get(i)[c - 'a']);
}
while (min-- > 0) {
res.add(String.valueOf(c));
}
}
return res;
} public int shortestDistance(String[] words, String word1, String word2) {
int ind1 = -1;
int ind2 = -1;
int min = Integer.MAX_VALUE;
for (int i = 0 ; i < words.length; i++) {
if (words[i].equals(word1)) {
ind1 = i;
} else if (words[i].equals(word2)) {
ind2 = i;
}
if (ind1 != -1 && ind2 != -1) min = Math.min(min, Math.abs(ind1 - ind2));
}
return min;
}Map<String, List<Integer>> map;
public WordDistance(String[] words) {
map = new HashMap<>();
for (int i = 0; i < words.length; i++) {
map.putIfAbsent(words[i], new ArrayList<>());
map.get(words[i]).add(i);
}
}
public int shortest(String word1, String word2) {
List<Integer> l1 = map.get(word1);
List<Integer> l2 = map.get(word2);
int i = 0, j = 0;
int min = Integer.MAX_VALUE;
while (i < l1.size() && j < l2.size()) {
int a = l1.get(i), b = l2.get(j);
min = Math.min(min, Math.abs(a - b));
if (a < b) {
i++;
} else {
j++;
}
}
return min;
}796. Rotate String
public boolean rotateString(String A, String B) {
if (A.isEmpty()) return B.isEmpty();
for (int i = 0; i < B.length(); i++) {
if (B.charAt(i) == A.charAt(0)) {
StringBuilder sb = new StringBuilder(B.substring(i));
sb.append(B.substring(0, i));
if (sb.toString().equals(A)) {
return true;
}
}
}
return false;
}Expand around the center, record the L and R when the length of palindromic substring is longer than R - L. return s.substring(L, R + 1).
int L = 0, R = 0;
public String longestPalindrome(String s) {
if (s == null || s.length() <= 1) return s;
for (int i = 0; i < s.length(); i++) {
expand(s, i, i);
expand(s, i, i + 1);
}
return s.substring(L, R + 1);
}
private void expand(String s, int i, int j) {
if (s.length() < 1) return;
while (i >= 0 && j < s.length() && s.charAt(i) == s.charAt(j)) {
if (j - i > R - L) {
L = i;
R = j;
}
i--;
j++;
}
}Sort and loop through. For example, "/a","/a/b","/c/d" you can remove "/a/b","/c/d" because they starts with "/a". T:O(nlogn)
public List<String> removeSubfolders(String[] folder) {
Arrays.sort(folder);
boolean[] remove = new boolean[folder.length];
for (int i = 0; i < folder.length; ) {
int j = i + 1;
while (j < folder.length
&& folder[j].startsWith(folder[i])
&& folder[j].substring(folder[i].length()).charAt(0) == '/') {
remove[j] = true;
j++;
}
i = j;
}
List<String> res = new ArrayList<>();
for (int i = 0; i < folder.length; i++) {
if (!remove[i]) res.add(folder[i]);
}
return res;
}A more elegant version:
public List<String> removeSubfolders(String[] folder) {
LinkedList<String> ans = new LinkedList<>();
Arrays.sort(folder);
for (String f : folder)
if (ans.isEmpty() || !f.startsWith(ans.peekLast() + '/')) // need '/' to ensure a parent.
ans.offer(f);
return ans;
}Trie. T: O(n * k) where k is average string length.
See section.
Swap x and y to make strings equal, there are three cases:
Case 1:
xx,yy=> minimum swap is 1Case 2:
xy,yx=> minimum swap is 2Case 3:
xy,xx=> not possible (have odd number of xy and yx)
case1 is calculated by xy / 2 + yx / 2, case 2 is calculated by xy % 2 + yx % 2
public int minimumSwap(String s1, String s2) {
int xy = 0, yx = 0;
for (int i = 0; i < Math.min(s1.length(), s2.length()); i++) {
char a = s1.charAt(i);
char b = s2.charAt(i);
if (a == b) continue;
if (a == 'x') {
xy++;
} else {
yx++;
}
}
if ((xy + yx) % 2 == 1) {
return -1;
}
return xy / 2 + yx / 2 + xy % 2 + yx % 2;
} public int expressiveWords(String S, String[] words) {
if (S == null || S.isEmpty() || words == null || words.length == 0) {
return 0;
}
int count = 0;
for (String w : words) {
if (helper(S, w)) {
count++;
}
}
return count;
}
private boolean helper(String s, String t) {
if (s.isEmpty() || t.isEmpty() || s.length() < t.length()) return false;
if (s.equals(t)) return true;
int i = 0, j = 0;
while (i < s.length()) {
if (i < s.length() && j < t.length() && s.charAt(i) == t.charAt(j)) {
i++;
j++;
} else if (i >= 2 && s.charAt(i) == s.charAt(i - 1) && s.charAt(i) == s.charAt(i - 2)) {
i++;
} else if (i >= 1 && i < s.length() - 1 && s.charAt(i) == s.charAt(i - 1) && s.charAt(i) == s.charAt(i + 1)) {
i++;
} else {
return false;
}
}
return j == t.length();
}It is a graph of mapping char vs char. Use a hashmap to store this relationship. When building the graph, we also have to validate if theres is any mismatch between the existing node. If yes, return false;
The cycle is detected when the number of relationships = 26. Which means there is a cycle of 26 lowercase characters. This is another false case.
public boolean canConvert(String str1, String str2) {
if (str1 == null || str2 == null || str1.length() != str2.length()) {
return false;
}
if (str1.equals(str2)) return true;
Map<Character, Character> map = new HashMap<>();
for (int i = 0; i < str1.length(); i++) {
char c1 = str1.charAt(i);
char c2 = str2.charAt(i);
if (map.containsKey(c1) && map.get(c1) != c2) {
return false;
}
map.put(c1, c2);
}
return new HashSet<Character>(map.values()).size() < 26;
}S = "abcd", indexes = [0,2], sources = ["a","cd"], targets = ["eee","ffff"].
Use a map of Index, String[]{source, target} to store the relationship.
public String findReplaceString(String S, int[] indexes, String[] sources, String[] targets) {
StringBuilder sb = new StringBuilder();
List<Node> list = new ArrayList<>();
for (int i = 0; i < indexes.length; i++) {
list.add(new Node(indexes[i], sources[i], targets[i]));
}
Collections.sort(list, (a, b) -> (a.index - b.index));
int i = 0, k = 0;
while (i < S.length()) {
while (i < S.length() && (k >= list.size() || i != list.get(k).index)) {
sb.append(S.charAt(i++));
}
if (k >= list.size()) continue;
String s = list.get(k).source;
if (i + s.length() <= S.length()
&& S.substring(i, i + s.length()).equals(s)) {
sb.append(list.get(k).target);
i += s.length();
k++;
} else if (i < S.length()) {
sb.append(S.charAt(i++));
}
}
return sb.toString();
}
class Node {
int index;
String source;
String target;
Node(int i, String s, String t) {
this.index = i;
this.source = s;
this.target = t;
}
public String licenseKeyFormatting(String S, int K) {
StringBuilder sb = new StringBuilder();
int count = 0;
for (int i = S.length() - 1; i >= 0; i--) {
char c = S.charAt(i);
if (count == K) {
count = 0;
sb.insert(0, "-");
}
if (Character.isDigit(c) || Character.isLetter(c)) {
sb.insert(0, Character.toUpperCase(c));
count++;
}
}
while (sb.length() != 0) {
if (Character.isDigit(sb.charAt(0)) || Character.isLetter(sb.charAt(0))) {
break;
} else {
sb.deleteCharAt(0);
}
}
return sb.toString();
}Use a hashmap to check the order between two characters. The total number of edges can't be larger and equal to 26 since it doesn't allow cycle in the graph.
public boolean canConvert(String str1, String str2) {
if (str1 == null || str1.length() == 0 || str2 == null || str2.length() == 0) {
return false;
}
if (str1.equals(str2)) {
return true;
}
Map<Character, Character> map = new HashMap<>();
for (int i = 0; i < Math.min(str1.length(), str2.length()); i++) {
char c1 = str1.charAt(i);
char c2 = str2.charAt(i);
if (map.containsKey(c1) && map.get(c1) != c2) {
return false;
}
map.put(c1, c2);
}
return new HashSet<Character>(map.values()).size() < 26;
}DFS to traverse and append strings, check if the string combo is unique.
T: O(2^N)
int max = 0;
public int maxLength(List<String> arr) {
dfs(arr, 0, new StringBuilder());
return max;
}
private void dfs(List<String> arr, int start, StringBuilder sb) {
if (!isUnique(sb.toString())) {
return;
}
max = Math.max(max, sb.length());
int len = sb.length();
for (int i = start; i < arr.size(); i++) {
sb.append(arr.get(i));
dfs(arr, i + 1, sb);
sb.setLength(len);
}
}
private boolean isUnique(String str) {
if (str.length() > 26) return false;
boolean[] used = new boolean [26];
char[] arr = str.toCharArray();
for (char ch : arr) {
if (used[ch - 'a']){
return false;
} else {
used[ch -'a'] = true;
}
}
return true;
}
public String[] createCardHands(String[] input) {
int n = input.length;
String[] res = new String[3];
for (int i = 0; i < n - 2; i++) {
for (int j = i + 1; j < n - 1; j++) {
for (int k = j + 1; k < n; k++) {
if (validSuits(input[i], input[j], input[k]) &&
validValue(input[i], input[j], input[k]) &&
validCount(input[i], input[j], input[k])) {
res[0] = input[i];
res[1] = input[j];
res[2] = input[k];
return res;
}
}
}
}
return res;
}
private static boolean validSuits(String a, String b, String c) {
Set<Character> set = new HashSet<>();
set.add(a.charAt(0));
set.add(b.charAt(0));
set.add(c.charAt(0));
return set.size() == 1 || set.size() == 3;
}
private static boolean validValue(String a, String b, String c) {
return (a.charAt(1) == b.charAt(1) && b.charAt(1) == c.charAt(1)) || (
a.charAt(1) != b.charAt(1)
&& b.charAt(1) != c.charAt(1)
&& a.charAt(1) != c.charAt(1)
);
}
private static boolean validCount(String a, String b, String c) {
Set<Integer> set = new HashSet<>();
set.add(a.substring(1).length());
set.add(b.substring(1).length());
set.add(c.substring(1).length());
return set.size() == 1 || set.size() == 3;
}
public Character getCode(Scanner scanner) {
String line;
int i = 0, x = -1, y = -1;
List<String> list = new ArrayList<>();
while (((line = scanner.nextLine()) != null) && !line.isEmpty()) {
if (i == 0) {
String[] strs = line.replace("[", "")
.replace("]", "").replace(" ", "")
.split(",");
y = Integer.parseInt(strs[0]);
x = Integer.parseInt(strs[1]);
} else {
list.add(line);
}
i++;
}
int m = list.size(), n = list.get(0).length();
if (x >= m || y >= n) return null;
return list.get(m - x - 1).charAt(y);
}
public static void main(String[] args) {
Scanner scanner = new Scanner(new BufferedInputStream(System.in));
ConstructPassword c = new ConstructPassword();
System.out.println(c.getCode(scanner));
}
public String genPassword(Scanner scanner) {
String line;
char[] chars = new char[100];
int consecutiveEmptyLines = 0, index = 0, x = 0, y = 0;
List<String> list = new ArrayList<>();
while ((line = scanner.nextLine()) != null && consecutiveEmptyLines <= 1) {
if (line.matches("[0-9]+")) { // digits
if (!list.isEmpty() && x < list.size() && y < list.get(0).length()) {
chars[index] = list.get(list.size() - x - 1).charAt(y);
list = new ArrayList<>();
}
consecutiveEmptyLines = 0;
index = Integer.parseInt(line);
} else if (line.indexOf('[') != -1) {
String[] strs = line.replace("[", "")
.replace("]", "").replace(" ", "")
.split(",");
y = Integer.parseInt(strs[0]);
x = Integer.parseInt(strs[1]);
} else if (!line.isEmpty()) {
list.add(line);
} else { // empty
consecutiveEmptyLines++;
}
}
if (!list.isEmpty()) {
chars[index] = list.get(list.size() - x - 1).charAt(y);
}
return new String(chars);
}
public static void main(String[] args) {
Scanner scanner = new Scanner(new BufferedInputStream(System.in));
ConstructPassword c = new ConstructPassword();
System.out.println(c.genPassword(scanner));
}Use two hashmaps to check the character relation.
public List<String> findAndReplacePattern(String[] words, String pattern) {
List<String> res = new ArrayList<>();
for (String w : words) {
if (match(w, pattern)) {
res.add(w);
}
}
return res;
}
private boolean match(String s, String p) {
if (s.length() != p.length()) return false;
Map<Character, Character> map = new HashMap<>();
Map<Character, Character> map2 = new HashMap<>();
for (int i = 0; i < s.length(); i++) {
char a = s.charAt(i);
char b = p.charAt(i);
if (map.containsKey(a) && map.get(a) != b) return false;
if (map2.containsKey(b) && map2.get(b) != a) return false;
map.put(a, b);
map2.put(b, a);
}
return true;
}Save all substrings with the same characters and its length to a list. Detect if the current and it is + 2 position substring has the same character, and their in between substring has 1 length.
The idea is to keep track of all repeated character segments and see if the neighbor segments (segments separated by one other character) can be merged:
There exist a third segment with same character, swap a same character from a third segment. Merged length = len(segment1) + 1 + len(segment2)
There does not exist a third segment with same character, swap a character from the first character of the first segment, or swapping the last character from the second segment, to the separating index. Merged length = len(segment1) + len(segment2)
Otherwise, if there are multiple segments of a character but they are not neighbor, we can only swap a character from one to the other. New length = len(segment) + 1
public int maxRepOpt1(String text) {
int[] freq = new int[26];
List<int[]> list = new ArrayList<>();
for (int i = 0, left = 0; i <= text.length(); i++) {
if (i < text.length()) freq[text.charAt(i) - 'a']++;
if (i == text.length() || text.charAt(i) != text.charAt(left)) {
list.add(new int[]{text.charAt(left), i - left});
left = i;
}
}
int res = 0;
for (int i = 0; i < list.size(); i++) {
int len = list.get(i)[1];
if (i + 2 < list.size() && list.get(i + 2)[0] == list.get(i)[0] && list.get(i + 1)[1] == 1) {
len += list.get(i + 2)[1];
}
res = Math.max(res, len + (len < freq[list.get(i)[0] - 'a'] ? 1 : 0));
}
return res;
}public String alphabetBoardPath(String target) {
StringBuilder ans = new StringBuilder();
int x = 0, y = 0;
for (char c : target.toCharArray()) {
int i = (c - 'a') / 5;
int j = (c - 'a') % 5;
if(i > x) {
while(x != i) {
if(x == 4 && y > 0 )
break;
ans.append("D");
x++;
}
} else {
while (x != i) {
ans.append("U");
x--;
}
}
if(j > y) {
while(y != j) {
ans.append("R");
y++;
}
} else {
while(y != j) {
ans.append("L");
y--;
}
}
if(x != i) {
ans.append("D");
x++;
}
ans.append("!");
}
return ans.toString();
}Determine if word is typo because of stuck key
Given a dictionary of valid words, write a function isTypoBecauseStuckKey() that accepts a string to determine if the string has a typo that is strictly caused by a stuck key.
Example:
Input: Dictionary: { hello, cat, world, dog, bird, grass, green, help, greet, great }
String: bbbirrrdddd
Output: True
Explanation: The character's 'b', 'r', & 'd' all repeat. Assuming their keys got stuck, we can form the word 'bird', which exists in the dictionary.
Example:
Input:
Dictionary: { hello, cat, world, dog, bird, grass, green, help, greet, great }
String: gggraasssa
Output: False
Explanation: The a at the end is not the result of a stuck key, and thus it is impossible for it to exist in the dictionary.
public static boolean istypo(String[] dictionary, String target) {
for (String s : dictionary) {
if (helper(s, target)) {
return true;
}
}
return false;
}
public static boolean helper(String s, String t) {
int j = 0;
for (int i = 0; i < t.length(); i++) {
if (j < s.length() && t.charAt(i) == s.charAt(j)) {
j++;
} else if (i > 0 &&t.charAt(i) == t.charAt(i - 1)) {
continue;
} else {
return false;
}
}
return j == s.length();
}Trie
public boolean istypo(String[] dictionary, String target) {
TrieNode root = new TrieNode();
for (String s : dictionary) {
addToTrie(root, s);
}
if (search(root, target.toCharArray(), 0)) return true;
return false;
}
private boolean search(TrieNode curt, char[] t, int index) {
if (curt == null) return false;
if (index == t.length) return curt.isEnd;
int id = t[index] - 'a';
if (search(curt.children[id], t, index + 1)) {
return true;
} else if (index > 0 && t[index - 1] == t[index] && search(curt, t, index + 1)) {
return true;
}
return false;
}
private void addToTrie(TrieNode root, String s) {
TrieNode curt = root;
for (int i = 0; i < s.length(); i++) {
int id = s.charAt(i) - 'a';
if (curt.children[id] == null) {
curt.children[id] = new TrieNode();
}
curt = curt.children[id];
}
curt.isEnd = true;
}
class TrieNode {
TrieNode[] children;
boolean isEnd;
TrieNode() {
this.children = new TrieNode[26];
}
}function applySubstitutions(replacements: string[][], text: string): string {
const map: Record<string, string> = {};
const keyListWithReplacement: string[] = [];
for (const [from, to] of replacements) {
map[from] = to;
if (to.includes("%")) {
keyListWithReplacement.push(from);
}
}
return replace(text, map);
}
function replace(t: string, map: Record<string, string>): string {
if (!t.includes("%")) {
return t;
}
const regex = /%(\w+)%/g;
let result = t;
for (const match of t.matchAll(regex)) {
const fullMatch = match[0];
const key = match[1];
if (Object.prototype.hasOwnProperty.call(map, key)) {
// Escape special regex chars in fullMatch
const escaped = fullMatch.replace(/[.*+?^${}()|[\]\\]/g, '\\$&');
const pattern = new RegExp(escaped, 'g');
result = result.replace(pattern, map[key]);
}
}
return replace(result, map);
}
Last updated
Was this helpful?