字串演算法與操作

# Python - Two pointers for palindrome
def isPalindrome(s):
    left, right = 0, len(s) - 1
    
    while left < right:
        # Skip non-alphanumeric
        while left < right and not s[left].isalnum():
            left += 1
        while left < right and not s[right].isalnum():
            right -= 1
        
        if s[left].lower() != s[right].lower():
            return False
        
        left += 1
        right -= 1
    
    return True

# Reverse string/array in-place
def reverseString(s):
    left, right = 0, len(s) - 1
    
    while left < right:
        s[left], s[right] = s[right], s[left]
        left += 1
        right -= 1
    
    return s

// Java - Two pointers
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;
}

# LC 242 Valid Anagram
def isAnagram(s, t):
    return Counter(s) == Counter(t)

# LC 438 Find All Anagrams in String (Sliding Window)
def findAnagrams(s, p):
    need = Counter(p)
    window = Counter()
    result = []
    for i, c in enumerate(s):
        window[c] += 1
        if i >= len(p):
            left = s[i - len(p)]
            window[left] -= 1
            if window[left] == 0: del window[left]
        if window == need:
            result.append(i - len(p) + 1)
    return result

# LC 49 Group Anagrams (sorted key)
def groupAnagrams(strs):
    from collections import defaultdict
    groups = defaultdict(list)
    for s in strs:
        groups[tuple(sorted(s))].append(s)
    return list(groups.values())

s = "001110011"

groups:
  00   -> 2
  111  -> 3
  00   -> 2
  11   -> 2

group lengths:  [2, 3, 2, 2]

adjacent pairs:
  min(2, 3) = 2      # "01", "0011"
  min(3, 2) = 2      # "10", "1100"
  min(2, 2) = 2      # "01", "0011"
--------------------
  total     = 6

# python
# IDEA: compress s into consecutive-group lengths, then work on that array
def group_lengths(s):
    groups = [1]
    for i in range(1, len(s)):
        # NOTE !!! boundary -> start a new group
        if s[i-1] != s[i]:
            groups.append(1)
        # same char -> extend current group
        else:
            groups[-1] += 1
    return groups

# LC 696 - Count Binary Substrings
# time = O(n), space = O(n)
def countBinarySubstrings(s):
    groups = group_lengths(s)
    ans = 0
    for i in range(1, len(groups)):
        # NOTE !!! each adjacent pair contributes min(prev, cur)
        ans += min(groups[i-1], groups[i])
    return ans

# one-liner with itertools.groupby
import itertools
def countBinarySubstrings_v2(s):
    groups = [len(list(v)) for _, v in itertools.groupby(s)]
    return sum(min(a, b) for a, b in zip(groups, groups[1:]))

# python
# IDEA: we never need the whole group array, only the 2 latest groups
# 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      # NOTE !!! cur becomes prev, restart cur
        else:
            cur += 1
    # NOTE !!! don't forget the LAST pair (loop never closes it)
    return ans + min(prev, cur)

// java
// LC 696 - Count Binary Substrings
// 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++;
        }
    }
    /** NOTE !!! flush the final group pair after the loop */
    return ans + Math.min(prev, cur);
}

# Python - String to integer (atoi)
def myAtoi(s):
    s = s.strip()
    if not s:
        return 0
    
    sign = 1
    idx = 0
    
    if s[0] in ['+', '-']:
        sign = -1 if s[0] == '-' else 1
        idx = 1
    
    num = 0
    while idx < len(s) and s[idx].isdigit():
        num = num * 10 + int(s[idx])
        idx += 1
    
    num *= sign
    
    # Handle overflow
    INT_MAX = 2**31 - 1
    INT_MIN = -2**31
    
    if num > INT_MAX:
        return INT_MAX
    if num < INT_MIN:
        return INT_MIN
    
    return num

# Integer to Roman
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 i, val in enumerate(values):
        count = num // val
        if count:
            result.append(symbols[i] * count)
            num -= val * count
    
    return ''.join(result)

// java
// LC 68 - Text Justification
// time = O(total chars), space = O(total chars) for the output
// IDEA: 2 phases per line -> (1) greedy pack words, (2) distribute leftover spaces
public List<String> fullJustify(String[] words, int maxWidth) {
    List<String> res = new ArrayList<>();
    int i = 0, n = words.length;
    while (i < n) {
        /** NOTE !!! (1) GREEDY PACK: widest [i, j) that fits with >= 1 space per gap
         *  (j - i) is the number of gaps if we also take words[j] */
        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 {
            /** NOTE !!! (2b) FULL JUSTIFY
             *  base = spaces / slots, and 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;   // NOTE !!! next line starts where this one stopped
    }
    return res;
}

# python
# LC 68 - Text Justification
# time = O(total chars), space = O(total chars) for the output
# IDEA: 2 phases per line -> (1) greedy pack words, (2) distribute leftover spaces
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])
                parts.append(" " * (base + (1 if k - i < extra else 0)))
            parts.append(words[j - 1])
            line = "".join(parts)
        res.append(line)
        i = j
    return res

// java
// LC 388 - Longest Absolute File Path
// time = O(n), space = O(max depth)
// IDEA: split on '\n'; leading '\t' count = depth; depthLen[d] = prefix length at depth d
public int lengthLongestPath(String input) {
    int best = 0;
    Map<Integer, Integer> depthLen = new HashMap<>();
    depthLen.put(0, 0);                       // root has empty prefix
    for (String line : input.split("\n")) {
        /** NOTE !!! depth == number of leading '\t' (tabs), NOT the indent width */
        int depth = 0;
        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 388 - Longest Absolute File Path
# time = O(n), space = O(max depth)
# IDEA: split on '\n'; leading '\t' count = depth; depth_len[d] = prefix length at depth d
def lengthLongestPath(inp):
    best = 0
    depth_len = {0: 0}                       # root has empty prefix
    for line in inp.split("\n"):
        name = line.lstrip("\t")
        depth = len(line) - len(name)        # NOTE !!! depth = number of leading tabs
        if "." in name:
            best = max(best, depth_len[depth] + len(name))   # file = leaf
        else:
            depth_len[depth + 1] = depth_len[depth] + len(name) + 1   # +1 for '/'
    return best

// java
// LC 71 - Simplify Path
// time = O(n), space = O(n)
// IDEA: split on '/', ignore "" and ".", ".." pops, everything else pushes
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();       // NOTE !!! popping empty root is a no-op
        } else {
            stack.offerLast(tok);
        }
    }
    StringBuilder sb = new StringBuilder();
    for (String d : stack) sb.append('/').append(d);
    return sb.length() == 0 ? "/" : sb.toString();
}

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

// java
// LC 1249 - Minimum Remove to Make Valid Parentheses
// time = O(n), space = O(n)
// IDEA: stack of '(' INDICES; unmatched ')' marked on sight, unmatched '(' left on the stack
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);                    // NOTE !!! push the INDEX
        } else if (arr[i] == ')') {
            if (stack.isEmpty()) arr[i] = '*';   // ')' with no partner -> mark for deletion
            else stack.pop();                    // matched pair
        }
        // letters are untouched
    }
    /** NOTE !!! whatever is still on the stack are unmatched '(' positions */
    while (!stack.isEmpty()) arr[stack.pop()] = '*';

    StringBuilder sb = new StringBuilder();
    for (char c : arr) if (c != '*') sb.append(c);
    return sb.toString();
}

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

// java
// LC 763 - Partition Labels
// time = O(n), space = O(1)  (26 letters)
// IDEA: last[c] = final index of c; extend `end` while scanning, cut when i reaches it
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++) {
        /** NOTE !!! the chunk must stretch to cover this char's last occurrence */
        end = Math.max(end, last[s.charAt(i) - 'a']);
        if (i == end) {                 // nothing inside reaches past i -> safe to cut
            res.add(end - start + 1);
            start = i + 1;
        }
    }
    return res;
}

# python
# LC 763 - Partition Labels
# time = O(n), space = O(1)  (26 letters)
# IDEA: last[c] = final index of c; extend `end` while scanning, cut when i reaches it
def partitionLabels(s):
    last = {c: i for i, c in enumerate(s)}   # dict comp keeps the LAST index
    res, start, end = [], 0, 0
    for i, c in enumerate(s):
        end = max(end, last[c])              # stretch the chunk
        if i == end:                         # safe cut point
            res.append(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)

// Java - Stack approach using |char1 - char2| == 32
public String makeGood(String s) {
    Stack<Character> stack = new Stack<>();

    for (char curr : s.toCharArray()) {
        if (!stack.isEmpty()) {
            char prev = stack.peek();

            /** NOTE !!
             *  core idea:
             *   The "Great" Condition: A pair is bad if |char1 - char2| == 32.
             *   Math.abs('a' - 'A') == 32.
             *   This checks if they are the same letter but different case.
             */
            if (Math.abs(curr - prev) == 32) {
                stack.pop(); // They cancel out — remove the pair
                continue;    // Move to next character
            }
        }
        stack.push(curr);
    }

    StringBuilder sb = new StringBuilder();
    for (char c : stack) {
        sb.append(c);
    }
    return sb.toString();
}

# Python equivalent
def makeGood(s: str) -> str:
    stack = []
    for c in s:
        if stack and abs(ord(stack[-1]) - ord(c)) == 32:
            stack.pop()  # Cancel the pair
        else:
            stack.append(c)
    return ''.join(stack)