String

744. Find Smallest Letter Greater Than Target

387. First Unique Character in a String

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;
}

953. Verifying an Alien Dictionary

Use a HashMap to record the order, verify the order and length.

Java

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();
} 

Python

415. Add Strings

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

819. Most Common Word

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;
    }

1002. Find Common Characters

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;
    } 

243. Shortest Word Distance

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;
}

244. Shortest Word Distance II

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

Java

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;
}

Java (One-line)

5. Longest Palindromic Substring

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++;
        }
    }

1233. Remove Sub-Folders from the Filesystem

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.

1247. Minimum Swaps to Make Strings Equal

Swap x and y to make strings equal, there are three cases:

1. Case 1: xx, yy => minimum swap is 1

2. Case 2: xy, yx => minimum swap is 2

3. 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;
    }

809. Expressive Words

    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();
    }

1153. String Transforms Into Another String

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;
    }

833. Find And Replace in String

S = "abcd", indexes = [0,2], sources = ["a","cd"], targets = ["eee","ffff"].

Use a map of Index, String[]{source, target} to store the relationship.

Java

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;
    }

Solution 1

722. Remove Comments

482. License Key Formatting

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();
}

1153. String Transforms Into Another String

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.

Java

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;
}

Python

1239. Maximum Length of a Concatenated String with Unique Characters

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;
}

Create Card Hands

Java

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;
}

DFS for all inputs

Construct Password from StdIn

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));
}

890. Find and Replace Pattern

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;
}

1156. Swap For Longest Repeated Character Substring

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:

1. There exist a third segment with same character, swap a same character from a third segment. Merged length = len(segment1) + 1 + len(segment2)

2. 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;
}

1138. Alphabet Board Path

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];
    }
}

3481. Apply Substitutions

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);
}

30. Substring with Concatenation of All Words

class Solution {
private:
    unordered_map<string, int> countMap;

    bool isMatch(string s) {
        unordered_map<string, int> counts = countMap;
        int len = countMap.begin()->first.size(); 
        int i = 0;
        while (i < s.size()) {
            string p = s.substr(i, len);
            if (!counts.count(p) || --counts[p] < 0) return false;
            i += len;
        }
        for (auto& [k, v] : counts) {
            if (v != 0) return false;
        }
        return true;
    }

public:
    vector<int> findSubstring(string s, vector<string>& words) {
        int len = words[0].size(); 
        int n = words.size(); // number of words
        for (string& w : words) {
            countMap[w]++;
        }
        vector<int> results;
        if (s.size() < len) return results;
        for (int i = 0; i < s.size() - n * len + 1; i++) {
            // if has count
            if (isMatch(s.substr(i, len * n))) {
                results.push_back(i);
            }
        }
        return results;
    }
};

443. String Compression

class Solution {
public:
    int compress(vector<char>& chars) {
        int i = 0;
        int n = chars.size();
        int res = 0;
        while (i < n) {
            int len = 1;
            while (i + len < n && chars[i] == chars[i + len]) {
                len++;
            }
            chars[res++] = chars[i];
            if (len > 1) {
                for (char c : to_string(len)) chars[res++] = c;
            }
            i += len;
        }
        return res;
    }
};

3136. Valid Word

class Solution:
    def isValid(self, word: str) -> bool:
        vowel = "aeiouAEIOU"
        hasVowel = False
        hasConsonant = False
        for c in word:
            if not c.isalnum():
                return False
            if c in vowel:
                hasVowel = True
            elif c.isalpha() and c not in vowel:
                hasConsonant = True
        return len(word) >= 3 and hasVowel and hasConsonant

2099. Find Subsequence of Length K With the Largest Sum

class Solution:
    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:
        index_nums = [(nums[i], i) for i in range(len(nums))]

        index_nums.sort(key=lambda x : x[0], reverse=True)

        k_largest = index_nums[:k]

        k_largest.sort(key=lambda x : x[1])
        
        return [val for val, idx in k_largest]

3597. Partition String

class Solution:
    def partitionString(self, s: str) -> List[str]:
        seen = set()
        result = []
        curt = ""

        for char in s:
            curt += char

            if curt not in seen:
                result.append(curt)
                seen.add(curt)
                curt = ""
        return result