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();
}
def isAlienSorted(self, words: List[str], order: str) -> bool:
dic = {}
for i, element in enumerate(order):
dic[element] = i
for i in range(len(words) - 1):
if not self.isValid(words[i], words[i + 1], dic):
return False;
return True;
def isValid(self, A, B, dic):
for i in range(min(len(A), len(B))):
if A[i] != B[i]:
return dic[A[i]] < dic[B[i]]
return len(A) <= len(B)
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_str
Use 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;
}
public boolean rotateString(String A, String B) {
return A.length() == B.length() && (A + A).contains(B);
}
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.
Swap x and y to make strings equal, there are three cases:
Case 1: xx, yy => minimum swap is 1
Case 2: xy, yx => minimum swap is 2
Case 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;
}
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 findReplaceString(String S, int[] indexes, String[] sources, String[] targets) {
Map<Integer, String[]> map = new HashMap<>();
for (int i = 0; i < indexes.length; i++) {
map.put(indexes[i], new String[]{sources[i], targets[i]});
}
StringBuilder sb = new StringBuilder();
int i = 0, appendLen = -1;
while (i < S.length()) {
if (map.containsKey(i)
&& map.get(i)[0].equals(
S.substring(i, Math.min(i + map.get(i)[0].length(), S.length())))) {
sb.append(map.get(i)[1]);
appendLen = map.get(i)[0].length();
} else {
sb.append(S.charAt(i));
appendLen = -1;
}
i += (appendLen == -1 ? 1 : appendLen);
}
return sb.toString();
}
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;
}
def canConvert(self, str1: str, str2: str) -> bool:
if len(str1) != len(str2):
return False
if str1 == str2:
return True
dic = {}
for i in range(len(str1)):
if str1[i] != str2[i]:
if str1[i] in dic and dic[str1[i]] != str2[i]:
return False;
dic[str1[i]] = str2[i]
values = set(dic.values())
return len(values) < 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 List<List<String>> createCardHands(String[] input) {
List<List<String>> res = new ArrayList<>();
dfs(input, new ArrayList<>(), 0, res);
return res;
}
private void dfs(String[] input, List<String> curtList, int index, List<List<String>> res) {
if (curtList.size() == 3) {
if (validCount(curtList.get(0), curtList.get(1), curtList.get(2))
&& validSuits(curtList.get(0), curtList.get(1), curtList.get(2))
&& validValue(curtList.get(0), curtList.get(1), curtList.get(2))) {
res.add(new ArrayList<>(curtList));
}
return;
}
for (int i = index; i < input.length; i++) {
curtList.add(input[i]);
dfs(input, curtList, i + 1, res);
curtList.remove(curtList.size() - 1);
}
}
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.
