# String

744\. Find Smallest Letter Greater Than Target

#### [387. First Unique Character in a String](https://leetcode.com/problems/first-unique-character-in-a-string/)

```java
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](https://leetcode.com/problems/verifying-an-alien-dictionary/)

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

{% tabs %}
{% tab title="Java" %}

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

{% endtab %}

{% tab title="Python" %}

```python
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)
```

{% endtab %}
{% endtabs %}

#### [415. Add Strings](https://leetcode.com/problems/add-strings/)

Add string from right to left, if there one string is out of digits, count as zero.&#x20;

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

```python
    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](https://leetcode.com/problems/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.&#x20;

*T: O(n)  S: O(n)*

```java
    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](https://leetcode.com/problems/find-common-characters/)

Convert each String to a map, get min count of all characters between 'a' and 'z'. Add the character to result.

```java
    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](https://leetcode.com/problems/shortest-word-distance/)

```java
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](https://leetcode.com/problems/shortest-word-distance-ii/)

```java
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

{% tabs %}
{% tab title="Java" %}

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

{% endtab %}

{% tab title="Java (One-line)" %}

```java
public boolean rotateString(String A, String B) {
    return A.length() == B.length() && (A + A).contains(B);
}
```

{% endtab %}
{% endtabs %}

#### [5. Longest Palindromic Substring](https://leetcode.com/problems/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)`.

```java
    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](https://leetcode.com/problems/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)*

```java
    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:

```java
    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](https://howardyangemail.gitbook.io/decode-leetcode/trie#1233-remove-sub-folders-from-the-filesystem).

#### [1247. Minimum Swaps to Make Strings Equal](https://leetcode.com/problems/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 &#x20;
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`

```java
    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](https://leetcode.com/problems/expressive-words/)

```java
    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](https://leetcode.com/problems/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.

```java
    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](https://leetcode.com/problems/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.

{% tabs %}
{% tab title="Java" %}

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

```

{% endtab %}

{% tab title="Solution 1" %}

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

{% endtab %}
{% endtabs %}

#### [722. Remove Comments](https://leetcode.com/problems/remove-comments/)

#### [482. License Key Formatting](https://leetcode.com/problems/license-key-formatting/)

```java
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](https://leetcode.com/problems/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**.

{% tabs %}
{% tab title="Java" %}

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

{% endtab %}

{% tab title="Python" %}

```python
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
```

{% endtab %}
{% endtabs %}

#### [1239. Maximum Length of a Concatenated String with Unique Characters](https://leetcode.com/problems/maximum-length-of-a-concatenated-string-with-unique-characters/)

DFS to traverse and append strings, check if the string combo is unique.

&#x20;*T: O(2^N)*

```java
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](https://leetcode.com/discuss/interview-question/554340/Instacart-or-Onsite-or-Create-Card-Hands)

![](https://249794273-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-Laur3QE_YAExtEZegFt%2F-MJXvZQ1sfqZbXb82BSQ%2F-MJXvqFvUTzKliUxgSto%2Fimage.png?alt=media\&token=2bdb6061-cc9b-4455-a971-1d40afa717e6)

{% tabs %}
{% tab title="Java" %}

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

{% endtab %}

{% tab title="DFS for all inputs" %}

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

{% endtab %}
{% endtabs %}

#### [Construct Password from StdIn](https://www.1point3acres.com/bbs/forum.php?mod=viewthread\&tid=667022)

![](https://249794273-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-Laur3QE_YAExtEZegFt%2F-MJUCK-0-StSjZVy8Mhz%2F-MJXsrbNTY-hylyrTeHV%2Fimage.png?alt=media\&token=cd8be4d4-a292-4479-9f5e-486c59fe2bd8)

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

![](https://249794273-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-Laur3QE_YAExtEZegFt%2F-MJUCK-0-StSjZVy8Mhz%2F-MJXsvD4U_ZGmf7Vx18B%2Fimage.png?alt=media\&token=afca9357-e705-4074-93a8-4cc715ec0c6d)

```java
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](https://leetcode.com/problems/find-and-replace-pattern/)

Use two hashmaps to check the character relation.

```java
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](https://leetcode.com/problems/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

```java
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](https://leetcode.com/problems/alphabet-board-path/)

```java
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.

```java
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

```java
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](https://leetcode.com/problems/apply-substitutions/)

```typescript
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](https://leetcode.com/problems/substring-with-concatenation-of-all-words/)

```cpp
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](https://leetcode.com/problems/string-compression/)

```cpp
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](https://leetcode.com/problems/valid-word/)

```python
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](https://leetcode.com/problems/find-subsequence-of-length-k-with-the-largest-sum/)

```python
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 ](https://leetcode.com/problems/partition-string/)

```python
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
```