String Algorithms — Worked Examples

# python
# LC 917 - Reverse Only Letters
# IDEA: left/right walk inward; a non-letter on either side is stepped over, two letters swap
# time = O(n), space = O(n) for the char list (strings are immutable)
def reverseOnlyLetters(s):
    chars = list(s)
    left, right = 0, len(chars) - 1
    while left < right:
        if not chars[left].isalpha():        # left is not a letter: it stays where it is
            left += 1
        elif not chars[right].isalpha():     # same on the right
            right -= 1
        else:                                # two letters: swap them and move both inward
            chars[left], chars[right] = chars[right], chars[left]
            left += 1
            right -= 1
    return "".join(chars)

// java
// LC 917 - Reverse Only Letters
// IDEA: left/right walk inward; a non-letter on either side is stepped over, two letters swap
// time = O(n), space = O(n) for the char array
public String reverseOnlyLetters(String s) {
    char[] chars = s.toCharArray();
    int left = 0, right = chars.length - 1;
    while (left < right) {
        if (!Character.isLetter(chars[left])) {
            left++;
        } else if (!Character.isLetter(chars[right])) {
            right--;
        } else {
            char tmp = chars[left];
            chars[left] = chars[right];
            chars[right] = tmp;
            left++;
            right--;
        }
    }
    return new String(chars);
}

s = "ab-cd"
[a b - c d]  left=0 right=4  both letters  swap -> [d b - c a]
[d b - c a]  left=1 right=3  both letters  swap -> [d c - b a]
             left=2 right=2  stop                -> "dc-ba"

# python
# LC 1794 - Count Pairs of Equal Substrings With Minimum Difference
# IDEA: char -> FIRST index in firstString, char -> LAST index in secondString; minimise the gap
# time = O(m + n), space = O(1)  (at most 26 keys per map)
def countQuadruples(firstString, secondString):
    first_idx = {}                      # char -> its FIRST index in firstString
    for i in range(len(firstString)):
        ch = firstString[i]
        if ch not in first_idx:
            first_idx[ch] = i
    last_idx = {}                       # char -> its LAST index in secondString
    for a in range(len(secondString)):
        last_idx[secondString[a]] = a   # later indices overwrite earlier ones
    min_diff = float('inf')
    count = 0
    for ch in first_idx:
        if ch not in last_idx:          # a char missing from secondString forms nothing
            continue
        diff = first_idx[ch] - last_idx[ch]
        if diff < min_diff:             # a strictly smaller diff restarts the count
            min_diff = diff
            count = 1
        elif diff == min_diff:          # an equal diff is one more quadruple
            count += 1
    return count

// java
// LC 1794 - Count Pairs of Equal Substrings With Minimum Difference
// IDEA: int[26] of last positions (+1, so 0 means absent); scan firstString once, first hits only
// time = O(m + n), space = O(1)
public int countQuadruples(String firstString, String secondString) {
    int[] last = new int[26];               // last[c] = last index of c in secondString, plus 1
    for (int a = 0; a < secondString.length(); a++) {
        last[secondString.charAt(a) - 'a'] = a + 1;
    }
    boolean[] seen = new boolean[26];       // only the FIRST occurrence in firstString counts
    int minDiff = Integer.MAX_VALUE, count = 0;
    for (int i = 0; i < firstString.length(); i++) {
        int c = firstString.charAt(i) - 'a';
        if (seen[c]) {
            continue;
        }
        seen[c] = true;
        if (last[c] == 0) {                 // 0 means c never appears in secondString
            continue;
        }
        int diff = i - (last[c] - 1);
        if (diff < minDiff) {
            minDiff = diff;
            count = 1;
        } else if (diff == minDiff) {
            count++;
        }
    }
    return count;
}

firstString = "abcd", secondString = "bccda"
char  first i  last a  i - a
 a       0       4      -4   <- minimum
 b       1       0       1
 c       2       2       0
 d       3       3       0          -> only 'a' reaches -4 -> answer 1

# python
# LC 720 - Longest Word in Dictionary
# IDEA: sort, then a word is buildable iff it has length 1 or word[:-1] is already buildable
# time = O(sum(L) log n) for the sort + O(sum(L)) for the slices, space = O(sum(L))
def longestWord(words):
    words = sorted(words)               # a prefix sorts before every word that extends it
    buildable = set()
    best = ""
    for word in words:
        if len(word) == 1 or word[:-1] in buildable:
            buildable.add(word)
            if len(word) > len(best):   # strictly longer: ties keep the earlier, smaller word
                best = word
    return best

// java
// LC 720 - Longest Word in Dictionary
// IDEA: sort, then a word is buildable iff it has length 1 or its one-shorter prefix is buildable
// time = O(sum(L) log n), space = O(sum(L))
public String longestWord(String[] words) {
    Arrays.sort(words);
    Set<String> buildable = new HashSet<>();
    String best = "";
    for (String word : words) {
        if (word.length() == 1 || buildable.contains(word.substring(0, word.length() - 1))) {
            buildable.add(word);
            if (word.length() > best.length()) {
                best = word;
            }
        }
    }
    return best;
}

# python
# LC 828 - Count Unique Characters of All Substrings of a Given String
# IDEA: per letter keep its last two positions; when a third arrives, the middle one's
#       contribution (prev1 - prev2) * (i - prev1) is final
# time = O(n), space = O(1)  (26 letters)
def uniqueLetterString(s):
    last_two = {}                       # char -> [second-to-last index, last index]
    total = 0
    for i, ch in enumerate(s):
        prev2, prev1 = last_two.get(ch, [-1, -1])
        # the occurrence at prev1 is unique in substrings that start in (prev2, prev1]
        # and end in [prev1, i): (prev1 - prev2) * (i - prev1) of them
        if prev1 != -1:
            total += (prev1 - prev2) * (i - prev1)
        last_two[ch] = [prev1, i]
    n = len(s)
    for prev2, prev1 in last_two.values():    # settle each char's final occurrence
        total += (prev1 - prev2) * (n - prev1)
    return total

s = "ABA"   (n = 3)
A at 0: prev = -1, next = 2  -> (0 - (-1)) * (2 - 0) = 2
B at 1: prev = -1, next = 3  -> (1 - (-1)) * (3 - 1) = 4
A at 2: prev =  0, next = 3  -> (2 - 0)    * (3 - 2) = 2
total = 8

# python
# LC 38 - Count and Say
# IDEA: n - 1 times, walk the term in groups of equal digits and write count then digit
# time = O(n * L) where L is the length of the longest term, space = O(L)
def countAndSay(n):
    term = "1"
    for _ in range(n - 1):
        parts = []
        i = 0
        while i < len(term):
            j = i
            while j < len(term) and term[j] == term[i]:   # j ends the group that starts at i
                j += 1
            parts.append(str(j - i))
            parts.append(term[i])
            i = j
        term = "".join(parts)
    return term

# python
# LC 809 - Expressive Words
# IDEA: walk s and the word together one group at a time; compare each pair of group lengths
# time = O(len(words) * len(s) + sum(len(w))): each word rescans s, space = O(1)
def expressiveWords(s, words):
    def stretchy(word):
        i = j = 0
        while i < len(s) and j < len(word):
            if s[i] != word[j]:
                return False
            ch = s[i]
            run_s = 0
            while i < len(s) and s[i] == ch:       # length of this group in s
                run_s += 1
                i += 1
            run_w = 0
            while j < len(word) and word[j] == ch: # length of the same group in word
                run_w += 1
                j += 1
            if run_s < run_w:                      # stretching only grows a group
                return False
            if run_s != run_w and run_s < 3:       # a grown group must reach 3
                return False
        return i == len(s) and j == len(word)      # both used up: same group sequence

    count = 0
    for word in words:
        if stretchy(word):
            count += 1
    return count

// java
// LC 809 - Expressive Words
// IDEA: walk s and the word together one group at a time; compare each pair of group lengths
// time = O(len(words) * len(s) + sum(len(w))): each word rescans s, space = O(1)
public int expressiveWords(String s, String[] words) {
    int count = 0;
    for (String word : words) {
        if (isStretchy(s, word)) {
            count++;
        }
    }
    return count;
}

private boolean isStretchy(String s, String word) {
    int i = 0, j = 0;
    while (i < s.length() && j < word.length()) {
        if (s.charAt(i) != word.charAt(j)) {
            return false;
        }
        char ch = s.charAt(i);
        int runS = 0;
        while (i < s.length() && s.charAt(i) == ch) {
            runS++;
            i++;
        }
        int runW = 0;
        while (j < word.length() && word.charAt(j) == ch) {
            runW++;
            j++;
        }
        if (runS < runW) {                    // stretching only grows a group
            return false;
        }
        if (runS != runW && runS < 3) {       // a grown group must reach 3
            return false;
        }
    }
    return i == s.length() && j == word.length();
}

s = "heeellooo"
word "hello": h 1|1  e 3|1 (>= 3, ok)  l 2|2  o 3|1 (>= 3, ok)  both used up -> match
word "helo":  h 1|1  e 3|1 (ok)        l 2|1 (2 < 3, fail)                    -> no
word "hi":    h 1|1  then 'e' != 'i'                                          -> no
answer = 1

# python
# LC 13 - Roman to Integer
# IDEA: scan right to left; subtract a symbol smaller than the one after it, else add
# time = O(n), space = O(1)
def romanToInt(s):
    value = {"I": 1, "V": 5, "X": 10, "L": 50, "C": 100, "D": 500, "M": 1000}
    total = 0
    prev = 0                            # value of the symbol to the right
    for i in range(len(s) - 1, -1, -1):
        cur = value[s[i]]
        if cur < prev:                  # a smaller symbol before a larger one subtracts
            total -= cur
        else:
            total += cur
        prev = cur
    return total

// java
// LC 13 - Roman to Integer
// IDEA: scan right to left; subtract a symbol smaller than the one after it, else add
// time = O(n), space = O(1)
public int romanToInt(String s) {
    Map<Character, Integer> value = new HashMap<>();
    value.put('I', 1);
    value.put('V', 5);
    value.put('X', 10);
    value.put('L', 50);
    value.put('C', 100);
    value.put('D', 500);
    value.put('M', 1000);
    int total = 0, prev = 0;
    for (int i = s.length() - 1; i >= 0; i--) {
        int cur = value.get(s.charAt(i));
        if (cur < prev) {
            total -= cur;
        } else {
            total += cur;
        }
        prev = cur;
    }
    return total;
}

# python
# LC 482 - License Key Formatting
# IDEA: scan right to left, skip dashes, upper-case, insert '-' each time a group of k fills
# time = O(n), space = O(n)
def licenseKeyFormatting(s, k):
    out = []                            # built right to left
    in_group = 0
    for i in range(len(s) - 1, -1, -1):
        if s[i] == '-':
            continue
        if in_group == k:               # the group on the right is full: open a new one
            out.append('-')
            in_group = 0
        out.append(s[i].upper())
        in_group += 1
    return "".join(reversed(out))

# python
# LC 468 - Validate IP Address
# IDEA: count separators to choose IPv4 / IPv6, split, validate each field against its rules
# time = O(n), space = O(n) for the split
def validIPAddress(queryIP):
    def is_ipv4(parts):
        for part in parts:
            if not 1 <= len(part) <= 3:
                return False
            if not all('0' <= c <= '9' for c in part):
                return False
            if len(part) > 1 and part[0] == '0':   # no leading zero
                return False
            if int(part) > 255:
                return False
        return True

    def is_ipv6(parts):
        hexdigits = "0123456789abcdefABCDEF"
        for part in parts:
            if not 1 <= len(part) <= 4:
                return False
            if not all(c in hexdigits for c in part):
                return False
        return True

    if queryIP.count('.') == 3 and is_ipv4(queryIP.split('.')):
        return "IPv4"
    if queryIP.count(':') == 7 and is_ipv6(queryIP.split(':')):
        return "IPv6"
    return "Neither"

# python
# LC 816 - Ambiguous Coordinates
# IDEA: for every comma position, cross the valid formats of the left and right halves
# time = O(n^4): O(n) commas x O(n) formats per half on each side x O(n) to build each string,
# space = O(n^4) for the output
def ambiguousCoordinates(s):
    def formats(part):
        out = []
        n = len(part)
        if n == 1 or part[0] != '0':            # whole number: no leading zero
            out.append(part)
        for i in range(1, n):                   # decimal: '.' after each interior position
            whole, frac = part[:i], part[i:]
            if len(whole) > 1 and whole[0] == '0':
                continue                        # "01.5": leading zero in the whole part
            if frac[-1] == '0':
                continue                        # "1.50": trailing zero in the fraction
            out.append(whole + "." + frac)
        return out

    digits = s[1:-1]
    result = []
    for i in range(1, len(digits)):             # the comma goes after digits[:i]
        for left in formats(digits[:i]):
            for right in formats(digits[i:]):
                result.append("(" + left + ", " + right + ")")
    return result

s = "(0123)"  ->  digits = "0123"
"0"   | "123"  ->  ["0"]  x ["123", "1.23", "12.3"]  ->  3
"01"  | "23"   ->  ["0.1"] x ["23", "2.3"]           ->  2
"012" | "3"    ->  ["0.12"] x ["3"]                  ->  1
total 6

# python
# LC 273 - Integer to English Words
# IDEA: split into 3-digit chunks low to high, spell each, tag with its scale, prepend
# time = O(1) (at most 4 chunks for a 32-bit int), space = O(1)
BELOW_20 = ["", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight",
            "Nine", "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen",
            "Sixteen", "Seventeen", "Eighteen", "Nineteen"]
TENS = ["", "", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"]
SCALES = ["", "Thousand", "Million", "Billion"]

def numberToWords(num):
    if num == 0:
        return "Zero"

    def three(n):                       # spell 1..999 as a list of words
        if n == 0:
            return []
        if n < 20:
            return [BELOW_20[n]]
        if n < 100:
            return [TENS[n // 10]] + three(n % 10)
        return [BELOW_20[n // 100], "Hundred"] + three(n % 100)

    parts = []
    scale = 0
    while num > 0:
        chunk = num % 1000
        if chunk != 0:                  # an all-zero chunk says nothing, not even its scale
            words = three(chunk)
            if scale > 0:
                words.append(SCALES[scale])
            parts = words + parts       # chunks arrive low to high: prepend
        num //= 1000
        scale += 1
    return " ".join(parts)

// java
// LC 273 - Integer to English Words
// IDEA: split into 3-digit chunks low to high, spell each, tag with its scale, prepend
// time = O(1) (at most 4 chunks for a 32-bit int), space = O(1)
private static final String[] BELOW_20 = {"", "One", "Two", "Three", "Four", "Five",
    "Six", "Seven", "Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen",
    "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
private static final String[] TENS = {"", "", "Twenty", "Thirty", "Forty", "Fifty",
    "Sixty", "Seventy", "Eighty", "Ninety"};
private static final String[] SCALES = {"", "Thousand", "Million", "Billion"};

public String numberToWords(int num) {
    if (num == 0) {
        return "Zero";
    }
    List<String> parts = new ArrayList<>();
    int scale = 0;
    while (num > 0) {
        int chunk = num % 1000;
        if (chunk != 0) {                     // an all-zero chunk says nothing
            List<String> words = three(chunk);
            if (scale > 0) {
                words.add(SCALES[scale]);
            }
            parts.addAll(0, words);           // chunks arrive low to high: prepend
        }
        num /= 1000;
        scale++;
    }
    return String.join(" ", parts);
}

private List<String> three(int n) {           // spell 1..999
    List<String> out = new ArrayList<>();
    if (n == 0) {
        return out;
    }
    if (n < 20) {
        out.add(BELOW_20[n]);
    } else if (n < 100) {
        out.add(TENS[n / 10]);
        out.addAll(three(n % 10));
    } else {
        out.add(BELOW_20[n / 100]);
        out.add("Hundred");
        out.addAll(three(n % 100));
    }
    return out;
}