Algorithmic Solutions: String Manipulation and Parsing

Posted on May 31, 2026 in Computer Engineering

String Duplicate Removal

def removeDuplicates(self, s: str, k: int) -> str:
    stack = []
    for char in s:
        if not stack:
            stack.append((char, 1))
        else:
            last_char, last_cnt = stack[-1]
            if char != last_char:
                stack.append((char, 1))
            else:
                if last_cnt + 1 < k:
                    stack[-1] = (last_char, last_cnt + 1)
                else:
                    stack.pop()
    return ''.join(c * cnt for c, cnt in stack)

Debugging Strategy

• Check logs
• Monitor metrics (e.g., memory usage)
• Reproduce with local input

For S3 streaming, maintain the stack state between chunks to handle edge cases where the end of one chunk matches the start of the next.

def process_stream(s3_chunks, k):
    stack = []
    for chunk in s3_chunks:
        for char in chunk:
            if stack and stack[-1][0] == char:
                last_char, last_cnt = stack[-1]
                if last_cnt + 1 == k:
                    stack.pop()
                else:
                    stack[-1] = (char, last_cnt + 1)
            else:
                stack.append((char, 1))
    return ''.join(c * cnt for c, cnt in stack)

Matrix Processing

Treat matrix rows as strings or flatten them based on requirements.

def removeDuplicatesMatrix(matrix, k):
    result = []
    for row in matrix:
        s = ''.join(row)
        result.append(removeDuplicates(s, k))
    return result

Crash Detection

Implement input validation, error handling, and logging.

import logging

def removeDuplicatesMatrix(matrix, k):
    if matrix is None:
        raise ValueError("matrix cannot be None")
    result = []
    for i, row in enumerate(matrix):
        try:
            logging.info(f"Processing row {i}")
            s = ''.join(row)
            result.append(removeDuplicates(s, k))
            logging.info(f"Row {i} done")
        except Exception as e:
            logging.error(f"Crash at row {i}: {e}")
            raise
    return result

Palindrome Logic

Clarification: Handle empty strings and special characters.

Approach: Use two pointers moving inward. Skip non-alphanumeric characters and ignore case. Time: O(n), Space: O(1).

def isPalindrome(s):
    l, r = 0, len(s) - 1
    while l < r:
        if not s[l].isalnum():
            l += 1
        elif not s[r].isalnum():
            r -= 1
        elif s[l].lower() == s[r].lower():
            l += 1
            r -= 1
        else:
            return False
    return True

Valid Palindrome (One Deletion): If s[l] != s[r], check if skipping either character results in a palindrome. Time: O(n), Space: O(n).

def validPalindrome(s):
    l, r = 0, len(s) - 1
    while l < r:
        if s[l] != s[r]:
            skip_l = s[l + 1 : r + 1]
            skip_r = s[l : r]
            return skip_l == skip_l[::-1] or skip_r == skip_r[::-1]
        l += 1
        r -= 1
    return True

Recursive Expression Parsing

Nested structures like ( MULT 3 ( ADD 3 4 ) ) are ideal for recursion. Use an index to track the current token.

def parse(expression):
    tokens = expression.split()
    i = 0
    def dfs(env):
        nonlocal i
        cur_token = tokens[i]
        i += 1
        if cur_token == "(":
            op = tokens[i]
            i += 1
            if op == "ADD":
                left = dfs(env)
                right = dfs(env)
                i += 1
                return left + right
            elif op == "MULT":
                left = dfs(env)
                right = dfs(env)
                i += 1
                return left * right
        else:
            return int(cur_token)
    return dfs({})

LET Expression Handling

1. Store variables in an env dictionary.
2. Copy env for each LET scope to maintain isolation.

def parse(expression):
    tokens = expression.split()
    i = 0
    def dfs(env):
        nonlocal i
        cur_token = tokens[i]
        i += 1
        if cur_token == "(":
            op = tokens[i]
            i += 1
            if op == "ADD":
                left = dfs(env)
                right = dfs(env)
                i += 1
                return left + right
            elif op == "MULT":
                left = dfs(env)
                right = dfs(env)
                i += 1
                return left * right
            elif op == "LET":
                local_env = env.copy()
                while True:
                    if tokens[i] == "(" or tokens[i+1] == ")":
                        result = dfs(local_env)
                        i += 1
                        return result
                    else:
                        var_name = tokens[i]
                        i += 1
                        local_env[var_name] = dfs(local_env)
        else:
            if cur_token[0].isdigit() or cur_token[0] == "-":
                return int(cur_token)
            else:
                return env[cur_token]
    return dfs({})