字串演算法與操作

# python
# LC 125 - Valid Palindrome
# IDEA: left/right walk inward, each skipping non-alphanumerics; compare case-folded
# time = O(n), space = O(1)
def isPalindrome(s):
    left, right = 0, len(s) - 1
    while left < right:
        while left < right and not s[left].isalnum():     # skip punctuation on the left
            left += 1
        while left < right and not s[right].isalnum():    # ... and on the right
            right -= 1
        if s[left].lower() != s[right].lower():
            return False
        left += 1
        right -= 1
    return True

# LC 344 - Reverse String: the same two pointers, swapping instead of comparing
def reverseString(s):
    left, right = 0, len(s) - 1
    while left < right:
        s[left], s[right] = s[right], s[left]
        left += 1
        right -= 1

// java
// LC 125 - Valid Palindrome
// IDEA: left/right walk inward, each skipping non-alphanumerics; compare case-folded
// time = O(n), space = O(1)
public boolean isPalindrome(String s) {
    int left = 0, right = s.length() - 1;
    while (left < right) {
        while (left < right && !Character.isLetterOrDigit(s.charAt(left))) {
            left++;
        }
        while (left < right && !Character.isLetterOrDigit(s.charAt(right))) {
            right--;
        }
        if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}

# python
# LC 242 - Valid Anagram
# IDEA: count s up and t down in one int[26]; anagrams iff every count returns to 0
# time = O(n), space = O(1)  (26 letters)
from collections import Counter, defaultdict

def isAnagram(s, t):
    if len(s) != len(t):
        return False
    count = [0] * 26
    for a, b in zip(s, t):
        count[ord(a) - ord('a')] += 1
        count[ord(b) - ord('a')] -= 1
    for c in count:
        if c != 0:
            return False
    return True

# LC 49 - Group Anagrams: the same signature, as a hash key
# time = O(n * k log k), k = longest word
def groupAnagrams(strs):
    groups = defaultdict(list)
    for word in strs:
        key = "".join(sorted(word))      # a list is unhashable; the joined string is not
        groups[key].append(word)
    return list(groups.values())

# LC 438 - Find All Anagrams in a String: the same signature, rolled across a window of len(p)
# time = O(n), space = O(1)  (26 letters)
def findAnagrams(s, p):
    need = Counter(p)
    window = Counter()
    result = []
    for i, c in enumerate(s):
        window[c] += 1
        if i >= len(p):                  # the window is one too long: drop its first char
            out = s[i - len(p)]
            window[out] -= 1
            if window[out] == 0:
                del window[out]
        if window == need:
            result.append(i - len(p) + 1)
    return result

// java
// LC 242 - Valid Anagram
// IDEA: count s up and t down in one int[26]; anagrams iff every count returns to 0
// time = O(n), space = O(1)
public boolean isAnagram(String s, String t) {
    if (s.length() != t.length()) {
        return false;
    }
    int[] count = new int[26];
    for (int i = 0; i < s.length(); i++) {
        count[s.charAt(i) - 'a']++;
        count[t.charAt(i) - 'a']--;
    }
    for (int c : count) {
        if (c != 0) {
            return false;
        }
    }
    return true;
}

// LC 49 - Group Anagrams: the sorted characters are the key
public List<List<String>> groupAnagrams(String[] strs) {
    Map<String, List<String>> groups = new HashMap<>();
    for (String word : strs) {
        char[] chars = word.toCharArray();
        Arrays.sort(chars);
        String key = new String(chars);
        groups.computeIfAbsent(key, k -> new ArrayList<>()).add(word);
    }
    return new ArrayList<>(groups.values());
}

# python
# LC 696 - Count Binary Substrings
# IDEA: compress s into consecutive-group lengths; each adjacent pair adds min(prev, cur)
# time = O(n), space = O(n)
def group_lengths(s):
    groups = [1]
    for i in range(1, len(s)):
        if s[i - 1] != s[i]:      # boundary: start a new group
            groups.append(1)
        else:                     # same char: extend the current group
            groups[-1] += 1
    return groups

def countBinarySubstrings(s):
    groups = group_lengths(s)
    ans = 0
    for i in range(1, len(groups)):
        ans += min(groups[i - 1], groups[i])
    return ans

# python
# LC 696 - Count Binary Substrings, streaming
# IDEA: never build the group array; keep prev (last finished group) and cur (open group)
# time = O(n), space = O(1)
def countBinarySubstrings(s):
    ans, prev, cur = 0, 0, 1
    for i in range(1, len(s)):
        if s[i - 1] != s[i]:
            ans += min(prev, cur)   # close off the boundary
            prev, cur = cur, 1      # the open group becomes prev; restart cur
        else:
            cur += 1
    return ans + min(prev, cur)     # the loop never closes the last pair

// java
// LC 696 - Count Binary Substrings
// IDEA: streaming run-length groups; each boundary adds min(prev, cur)
// time = O(n), space = O(1)
public int countBinarySubstrings(String s) {
    int ans = 0, prev = 0, cur = 1;
    for (int i = 1; i < s.length(); i++) {
        if (s.charAt(i) != s.charAt(i - 1)) {
            ans += Math.min(prev, cur);
            prev = cur;
            cur = 1;
        } else {
            cur++;
        }
    }
    return ans + Math.min(prev, cur);   // flush the final pair
}

s = "001110011"
groups:        00 | 111 | 00 | 11   ->  [2, 3, 2, 2]
min(2, 3) = 2  "01", "0011"
min(3, 2) = 2  "10", "1100"
min(2, 2) = 2  "01", "0011"
total     = 6

# python
# LC 8 - String to Integer (atoi)
# IDEA: one index, three phases (leading spaces, one sign, digits); clamp as each digit lands
# time = O(n), space = O(1)
def myAtoi(s):
    INT_MAX, INT_MIN = 2**31 - 1, -2**31
    i, n = 0, len(s)
    while i < n and s[i] == ' ':           # phase 1: leading spaces only
        i += 1
    sign = 1
    if i < n and s[i] in '+-':             # phase 2: at most one sign
        if s[i] == '-':
            sign = -1
        i += 1
    num = 0
    while i < n and '0' <= s[i] <= '9':    # phase 3: digits until the first non-digit
        num = num * 10 + (ord(s[i]) - ord('0'))
        if sign * num > INT_MAX:
            return INT_MAX
        if sign * num < INT_MIN:
            return INT_MIN
        i += 1
    return sign * num

# LC 12 - Integer to Roman: the rebuild direction — greedy over the value/symbol table,
# where the subtractive pairs (900 "CM", 4 "IV") are just more rows
def intToRoman(num):
    values = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]
    symbols = ["M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"]
    result = []
    for value, symbol in zip(values, symbols):
        while num >= value:
            result.append(symbol)
            num -= value
    return "".join(result)

// java
// LC 8 - String to Integer (atoi)
// IDEA: one index, three phases; test for overflow BEFORE num * 10 + digit can wrap
// time = O(n), space = O(1)
public int myAtoi(String s) {
    int i = 0, n = s.length();
    while (i < n && s.charAt(i) == ' ') {
        i++;
    }
    int sign = 1;
    if (i < n && (s.charAt(i) == '+' || s.charAt(i) == '-')) {
        if (s.charAt(i) == '-') {
            sign = -1;
        }
        i++;
    }
    int num = 0;
    while (i < n && s.charAt(i) >= '0' && s.charAt(i) <= '9') {   // ASCII digits only
        int digit = s.charAt(i) - '0';
        if (num > (Integer.MAX_VALUE - digit) / 10) {   // num * 10 + digit would overflow
            return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
        }
        num = num * 10 + digit;
        i++;
    }
    return sign * num;
}

# python
# LC 68 - Text Justification
# IDEA: 2 phases per line -> (1) greedy pack words, (2) distribute leftover spaces
# time = O(total chars), space = O(total chars) for the output
def fullJustify(words, maxWidth):
    res, i, n = [], 0, len(words)
    while i < n:
        # (1) GREEDY PACK: widest [i, j) that fits with >= 1 space per gap
        j, lineLen = i, 0
        while j < n and lineLen + len(words[j]) + (j - i) <= maxWidth:
            lineLen += len(words[j])
            j += 1
        slots = j - i - 1                 # gaps between the packed words
        spaces = maxWidth - lineLen       # spaces to spread over those gaps

        if j == n or slots == 0:
            # (2a) LAST LINE or SINGLE WORD -> left justify, pad the right
            line = " ".join(words[i:j])
            line += " " * (maxWidth - len(line))
        else:
            # (2b) FULL JUSTIFY: first (spaces % slots) gaps get one extra space
            base, extra = divmod(spaces, slots)
            parts = []
            for k in range(i, j - 1):
                parts.append(words[k])
                gap = base + (1 if k - i < extra else 0)
                parts.append(" " * gap)
            parts.append(words[j - 1])
            line = "".join(parts)
        res.append(line)
        i = j                             # the next line starts where this one stopped
    return res

// java
// LC 68 - Text Justification
// IDEA: 2 phases per line -> (1) greedy pack words, (2) distribute leftover spaces
// time = O(total chars), space = O(total chars) for the output
public List<String> fullJustify(String[] words, int maxWidth) {
    List<String> res = new ArrayList<>();
    int i = 0, n = words.length;
    while (i < n) {
        // (1) GREEDY PACK: (j - i) is the number of gaps if words[j] is also taken
        int j = i, lineLen = 0;
        while (j < n && lineLen + words[j].length() + (j - i) <= maxWidth) {
            lineLen += words[j].length();
            j++;
        }
        int slots = j - i - 1;             // gaps between the packed words
        int spaces = maxWidth - lineLen;   // spaces to spread over those gaps

        StringBuilder sb = new StringBuilder();
        if (j == n || slots == 0) {
            // (2a) LAST LINE or SINGLE WORD -> left justify, pad the right
            for (int k = i; k < j; k++) {
                if (k > i) {
                    sb.append(' ');
                }
                sb.append(words[k]);
            }
            while (sb.length() < maxWidth) {
                sb.append(' ');
            }
        } else {
            // (2b) FULL JUSTIFY: base = spaces / slots, the first (spaces % slots) gaps get +1
            int base = spaces / slots, extra = spaces % slots;
            for (int k = i; k < j; k++) {
                sb.append(words[k]);
                if (k < j - 1) {
                    int pad = base + (k - i < extra ? 1 : 0);
                    for (int p = 0; p < pad; p++) {
                        sb.append(' ');
                    }
                }
            }
        }
        res.add(sb.toString());
        i = j;   // the next line starts where this one stopped
    }
    return res;
}

# python
# LC 388 - Longest Absolute File Path
# IDEA: split on '\n'; leading '\t' count = depth; depth_len[d] = prefix length at depth d
# time = O(n), space = O(max depth)
def lengthLongestPath(inp):
    best = 0
    depth_len = {0: 0}                       # root has an empty prefix
    for line in inp.split("\n"):
        name = line.lstrip("\t")
        depth = len(line) - len(name)        # depth = number of leading tabs
        if "." in name:
            best = max(best, depth_len[depth] + len(name))         # a file is a leaf
        else:
            depth_len[depth + 1] = depth_len[depth] + len(name) + 1  # +1 for '/'
    return best

// java
// LC 388 - Longest Absolute File Path
// IDEA: split on '\n'; leading '\t' count = depth; depthLen[d] = prefix length at depth d
// time = O(n), space = O(max depth)
public int lengthLongestPath(String input) {
    int best = 0;
    Map<Integer, Integer> depthLen = new HashMap<>();
    depthLen.put(0, 0);                       // root has an empty prefix
    for (String line : input.split("\n")) {
        int depth = 0;                        // number of leading '\t', not the indent width
        while (depth < line.length() && line.charAt(depth) == '\t') {
            depth++;
        }
        String name = line.substring(depth);
        if (name.indexOf('.') >= 0) {
            // a FILE: it is a leaf -> only measure, never push
            best = Math.max(best, depthLen.get(depth) + name.length());
        } else {
            // a DIRECTORY: children live at depth+1, +1 for the '/' separator
            depthLen.put(depth + 1, depthLen.get(depth) + name.length() + 1);
        }
    }
    return best;
}

# python
# LC 71 - Simplify Path
# IDEA: split on '/', ignore "" and ".", ".." pops, everything else pushes
# time = O(n), space = O(n)
def simplifyPath(path):
    stack = []
    for tok in path.split("/"):
        if tok == "" or tok == ".":          # "//" and "/./" are no-ops
            continue
        if tok == "..":
            if stack:                        # ".." at the root stays at the root
                stack.pop()
        else:
            stack.append(tok)
    return "/" + "/".join(stack)

// java
// LC 71 - Simplify Path
// IDEA: split on '/', ignore "" and ".", ".." pops, everything else pushes
// time = O(n), space = O(n)
public String simplifyPath(String path) {
    Deque<String> stack = new ArrayDeque<>();
    for (String tok : path.split("/")) {
        if (tok.isEmpty() || tok.equals(".")) {
            continue;                                // "//" and "/./" are no-ops
        }
        if (tok.equals("..")) {
            if (!stack.isEmpty()) {
                stack.pollLast();                    // ".." at the root stays at the root
            }
        } else {
            stack.offerLast(tok);
        }
    }
    StringBuilder sb = new StringBuilder();
    for (String dir : stack) {
        sb.append('/').append(dir);
    }
    return sb.length() == 0 ? "/" : sb.toString();
}

# python
# LC 1249 - Minimum Remove to Make Valid Parentheses
# IDEA: stack of '(' INDICES; unmatched ')' blanked on sight, unmatched '(' left on the stack
# time = O(n), space = O(n)
def minRemoveToMakeValid(s):
    arr = list(s)
    stack = []
    for i, c in enumerate(arr):
        if c == "(":
            stack.append(i)          # push the index, not the char
        elif c == ")":
            if stack:
                stack.pop()          # matched pair
            else:
                arr[i] = ""          # ')' with no partner -> blank it out
    for i in stack:                  # leftovers = unmatched '(' positions
        arr[i] = ""
    return "".join(arr)

// java
// LC 1249 - Minimum Remove to Make Valid Parentheses
// IDEA: stack of '(' INDICES; unmatched ')' marked on sight, unmatched '(' left on the stack
// time = O(n), space = O(n)
public String minRemoveToMakeValid(String s) {
    char[] arr = s.toCharArray();
    Deque<Integer> stack = new ArrayDeque<>();
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == '(') {
            stack.push(i);                   // push the index, not the char
        } else if (arr[i] == ')') {
            if (stack.isEmpty()) {
                arr[i] = '*';                // ')' with no partner -> mark for deletion
            } else {
                stack.pop();                 // matched pair
            }
        }
    }
    while (!stack.isEmpty()) {               // leftovers = unmatched '(' positions
        arr[stack.pop()] = '*';
    }
    StringBuilder sb = new StringBuilder();
    for (char c : arr) {
        if (c != '*') {
            sb.append(c);
        }
    }
    return sb.toString();
}

# python
# LC 763 - Partition Labels
# IDEA: last[c] = final index of c; extend `end` while scanning, cut when i reaches it
# time = O(n), space = O(1)  (26 letters)
def partitionLabels(s):
    last = {}
    for i, c in enumerate(s):      # pass 1: the last index of every character
        last[c] = i
    res = []
    start = end = 0
    for i, c in enumerate(s):      # pass 2: stretch the chunk, cut when it closes
        end = max(end, last[c])
        if i == end:
            res.append(end - start + 1)
            start = i + 1
    return res

// java
// LC 763 - Partition Labels
// IDEA: last[c] = final index of c; extend `end` while scanning, cut when i reaches it
// time = O(n), space = O(1)  (26 letters)
public List<Integer> partitionLabels(String s) {
    int[] last = new int[26];
    for (int i = 0; i < s.length(); i++) {
        last[s.charAt(i) - 'a'] = i;         // last occurrence
    }
    List<Integer> res = new ArrayList<>();
    int start = 0, end = 0;
    for (int i = 0; i < s.length(); i++) {
        end = Math.max(end, last[s.charAt(i) - 'a']);   // stretch to cover this char
        if (i == end) {                      // nothing inside reaches past i -> safe to cut
            res.add(end - start + 1);
            start = i + 1;
        }
    }
    return res;
}

Math.abs('a' - 'A') == 32   // true
Math.abs('z' - 'Z') == 32   // true
Math.abs('a' - 'B') == 33   // false (different letters)

# python
# LC 1544 - Make The String Great
# IDEA: stack; a char that is the top's other-case twin (|diff| == 32) cancels it, else push
# time = O(n), space = O(n)
def makeGood(s):
    stack = []
    for ch in s:
        if stack and abs(ord(stack[-1]) - ord(ch)) == 32:   # same letter, other case
            stack.pop()                                      # the pair cancels
        else:
            stack.append(ch)
    return "".join(stack)

// java
// LC 1544 - Make The String Great
// IDEA: stack; a char that is the top's other-case twin (|diff| == 32) cancels it, else push
// time = O(n), space = O(n)
public String makeGood(String s) {
    Deque<Character> stack = new ArrayDeque<>();
    for (char ch : s.toCharArray()) {
        if (!stack.isEmpty() && Math.abs(stack.peek() - ch) == 32) {
            stack.pop();                     // same letter, other case: the pair cancels
        } else {
            stack.push(ch);
        }
    }
    StringBuilder sb = new StringBuilder();
    while (!stack.isEmpty()) {
        sb.append(stack.pollLast());         // bottom of the stack is the front of the answer
    }
    return sb.toString();
}