String Interview Problems for Embedded Engineers

Key Insight: A palindrome reads the same forwards and backwards. By using two pointers converging from both ends and skipping non-alphanumeric characters, we avoid creating a filtered copy of the string — keeping space at O(1).

Thought Process:

1. Place one pointer at the start and one at the end of the string.
2. Skip any non-alphanumeric characters by advancing/decrementing the respective pointer.
3. Compare the lowercase versions of the characters at both pointers — if they differ, it is not a palindrome.
4. Move both pointers inward and repeat until they meet.

Time Complexity: O(n) — single pass through the string with two pointers. Space Complexity: O(1) — no extra data structures, comparison done in-place.

class Solution {
public:
    bool isPalindrome(string s) {
        int st = 0;
        int end = s.size() - 1;

        while (st < end) {
            if (!isalnum(s[st]) || !isalnum(s[end])) {
                while (st < end && !isalnum(s[st])) st++;
                while (st < end && !isalnum(s[end])) end--;
            } else {
                if (tolower(s[st]) != tolower(s[end]))
                    return false;
                st++;
                end--;
            }
        }

        return true;
    }
};

Key Insight: Brute force substring search is perfectly acceptable here. For each valid starting position in the haystack, compare character by character with the needle. The O(1) space and simplicity make it ideal for embedded — no preprocessing tables needed.

Thought Process:

1. Edge case: if the needle is empty, return 0. If the haystack is shorter than the needle, return -1.
2. Iterate through each position in the haystack where the needle could start (indices 0 through len(haystack) - len(needle)).
3. At each starting position, compare the haystack substring with the needle character by character.
4. If all characters match, return the starting index. If a mismatch occurs, break and try the next position.
5. If no match is found after all positions, return -1.

Time Complexity: O((N-M) * M) — for each of the N-M+1 starting positions, up to M comparisons. Space Complexity: O(1) — no extra memory, comparison done in-place.

class Solution {
public:
    int strStr(string& source, string& target) {
        if (source.size() < target.size()) return -1;
        if (target.size() == 0) return 0;

        for (int ret = 0; ret < source.size() - target.size() + 1; ret++) {
            if (source[ret] == target[0]) {
                for (int i = 0; i < target.size(); i++) {
                    if (source[ret + i] != target[i])
                        break;
                    else if (i == target.size() - 1)
                        return ret;
                }
            }
        }
        return -1;
    }
};

Embedded relevance: This is essentially what strstr() from <string.h> does — a function you use constantly when parsing command responses, log messages, and protocol headers in firmware.

Key Insight: Use the standard two-pointer palindrome check, but when a mismatch is found, you get one chance — skip either the left character or the right character, and check if the remaining substring is a palindrome. If either skip works, the answer is true.

Thought Process:

1. Start with two pointers at both ends of the string, converging inward.
2. If characters match, move both pointers inward as usual.
3. On the first mismatch, try two options: skip the left character (check substring [i+1..j]) or skip the right character (check substring [i..j-1]).
4. If either remaining substring is a palindrome, return true. Otherwise, return false.
5. A helper function isPalin(s, start, end) performs the standard palindrome check on a substring.

Time Complexity: O(n) — at most two linear scans of the string. Space Complexity: O(1) — only pointer variables, no extra data structures.

class Solution {
public:
    bool isPalin(string& s, int start, int end) {
        while (start < end) {
            if (s[start] != s[end]) return false;
            ++start;
            --end;
        }
        return true;
    }

    bool validPalindrome(string s) {
        for (int i = 0, j = s.size() - 1; i < j; ++i, --j) {
            if (s[i] != s[j]) {
                return (isPalin(s, i, j - 1) || isPalin(s, i + 1, j));
            }
        }
        return true;
    }
};

Key Insight: The nested bracket structure maps naturally to a stack. Each [ creates a new context (saving the current count and accumulated string), and each ] pops a context and repeats the inner string by the saved count.

Thought Process:

1. Maintain a stack of (count, string) pairs representing nested decode contexts.
2. When encountering a digit, build the multi-digit number (multiply accumulated number by 10 and add new digit).
3. When encountering [, push the current count onto the stack with an empty string, then reset the count.
4. When encountering ], pop the top of the stack. Repeat the accumulated inner string by the popped count. Append the result to the next stack entry (or to the final result if the stack is empty).
5. When encountering a letter, append it to the current context (top of stack or result string).

Time Complexity: O(maxK * n) — in the worst case, each character may be repeated up to maxK times. Space Complexity: O(m + n) — stack depth proportional to nesting, plus the output string.

class Solution {
public:
    string decodeString(string s) {
        stack<pair<int, string>> decode_stk;
        string ret = "";
        int number = 0;

        for (int i = 0; i < s.size(); i++) {
            if (s[i] == '[') {
                string encode_str = "";
                decode_stk.push(make_pair(number, encode_str));
                number = 0;
            } else if (s[i] == ']') {
                pair<int, string> tmp = decode_stk.top();
                decode_stk.pop();
                string copy = tmp.second;
                while (--tmp.first) copy += tmp.second;

                if (decode_stk.empty()) {
                    ret += copy;
                } else {
                    auto& top = decode_stk.top();
                    top.second += copy;
                }
            } else if (isalpha(s[i])) {
                if (decode_stk.empty()) {
                    ret += s[i];
                } else {
                    decode_stk.top().second += s[i];
                }
            } else if (isdigit(s[i])) {
                number = number * 10 + s[i] - '0';
            }
        }

        return ret;
    }
};

Key Insight: An anagram is just a rearrangement — two strings are anagrams if and only if they have identical character frequencies. By sliding a fixed-size window across s and maintaining a frequency map, we can check for anagram matches in O(1) per step.

Thought Process:

1. Build a frequency map for the pattern p.
2. Slide a window of size |p| across s. Maintain a frequency map for the current window.
3. When the window reaches size |p|, compare the two frequency maps. If they match, the window start index is an anagram position.
4. Slide the window forward: add the new right character and remove the leftmost character.
5. Optimization: if the incoming character is not in p at all, clear the window map and jump the start pointer past it.

Time Complexity: O(Ns + Np) — one pass to build the pattern map, one pass to slide the window. Space Complexity: O(1) — frequency maps have at most 26 entries (lowercase English letters).

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        unordered_map<char, int> p_umap, s_umap;
        vector<int> ret;

        if (s.size() < p.size()) return ret;

        for (auto c : p) p_umap[c]++;

        int st = 0, end = 0;

        while (end < s.size()) {
            if (end - st + 1 < p.size()) {
                if (p_umap.find(s[end]) != p_umap.end()) {
                    s_umap[s[end]]++;
                    end++;
                } else {
                    s_umap.clear();
                    end++;
                    st = end;
                }
            } else if (end - st + 1 > p.size()) {
                if (s_umap[s[st]] == 1)
                    s_umap.erase(s[st]);
                else
                    s_umap[s[st]]--;
                st++;
            } else {
                s_umap[s[end]]++;
                if (s_umap == p_umap) ret.push_back(st);
                end++;
            }
        }

        return ret;
    }
};

Embedded relevance: Sliding window with frequency counting is the same pattern used for detecting byte sequences in serial protocol streams — matching known command patterns within a continuous data flow.

Key Insight: Reverse the entire string first, then reverse each individual word. This two-pass reverse trick achieves in-place word reversal without extra memory — a classic embedded technique.

Thought Process:

1. Reverse the entire string character by character. Now all words are in the correct order but each word is backwards.
2. Walk through the reversed string, identifying word boundaries (spaces).
3. Reverse each individual word in-place to restore correct spelling.
4. Handle edge cases: leading/trailing spaces, multiple consecutive spaces between words.
5. This approach uses O(1) extra space since all operations are in-place swaps.

Time Complexity: O(n) — two passes over the string (full reverse + per-word reverse). Space Complexity: O(1) — all operations are in-place character swaps.

class Solution {
public:
    string reverseWords(string s) {
        // Step 1: Reverse the entire string
        reverse(s.begin(), s.end());

        int n = s.size();
        int idx = 0;

        for (int start = 0; start < n; start++) {
            if (s[start] == ' ') continue;

            // Add space before word (except the first)
            if (idx != 0) s[idx++] = ' ';

            // Copy word characters
            int end = start;
            while (end < n && s[end] != ' ') {
                s[idx++] = s[end++];
            }

            // Step 2: Reverse the word in-place
            reverse(s.begin() + idx - (end - start), s.begin() + idx);
            start = end;
        }

        s.erase(s.begin() + idx, s.end());
        return s;
    }
};

Embedded relevance: In-place string reversal is used in embedded systems for display formatting, log message reordering, and preparing output buffers without heap allocation.

Key Insight: Count character frequencies in one pass, then scan again to find the first character with count 1. The frequency array is bounded at 26 (or 256 for ASCII), so space is O(1).

Thought Process:

1. First pass: build a frequency count for every character in the string using an array of size 26 (for lowercase) or 256 (for full ASCII).
2. Second pass: iterate through the string again, and for each character, check if its frequency is exactly 1.
3. Return the index of the first character with frequency 1.
4. If no such character exists, return -1.
5. The two-pass approach is necessary because the first unique character by position may not be the first one encountered during frequency counting.

Time Complexity: O(n) — two linear passes over the string. Space Complexity: O(1) — fixed-size frequency array (26 or 256 entries regardless of input size).

class Solution {
public:
    int firstUniqChar(string s) {
        int freq[26] = {0};

        for (char c : s) freq[c - 'a']++;

        for (int i = 0; i < s.size(); i++) {
            if (freq[s[i] - 'a'] == 1) return i;
        }

        return -1;
    }
};

Embedded relevance: Character frequency counting with fixed-size arrays is a staple of embedded text processing — used in command parsing, checksum validation, and protocol field extraction.

Key Insight: This is a state machine problem: skip whitespace, detect sign, then accumulate digits while checking for overflow before each multiply-and-add. The overflow check must happen before the multiplication to avoid undefined behavior.

Thought Process:

1. Skip leading whitespace characters.
2. Check for an optional + or - sign and record the sign.
3. Process consecutive digit characters: multiply the result by 10 and add the digit value.
4. Before each multiplication, check if the result would overflow INT_MAX or underflow INT_MIN. If so, clamp to the boundary.
5. Stop at the first non-digit character (including end of string). Return the accumulated result with the correct sign.

Time Complexity: O(n) — single pass through the string. Space Complexity: O(1) — only a few integer variables.

class Solution {
public:
    int myAtoi(string s) {
        int i = 0, sign = 1;
        long result = 0;

        // Skip whitespace
        while (i < s.size() && s[i] == ' ') i++;

        // Handle sign
        if (i < s.size() && (s[i] == '+' || s[i] == '-')) {
            sign = (s[i] == '-') ? -1 : 1;
            i++;
        }

        // Process digits
        while (i < s.size() && isdigit(s[i])) {
            result = result * 10 + (s[i] - '0');
            if (result * sign > INT_MAX) return INT_MAX;
            if (result * sign < INT_MIN) return INT_MIN;
            i++;
        }

        return (int)(result * sign);
    }
};

Embedded relevance: Implementing atoi is a rite of passage for embedded engineers — you need it for parsing AT command responses, configuration files, and sensor readings when the standard library is unavailable or too heavy.

Key Insight: This is grade-school addition — process digit by digit from right to left, propagating carry. The constraint against integer conversion forces you to work character by character, which is actually how embedded systems handle BCD and multi-precision arithmetic.

Thought Process:

1. Start from the rightmost digits of both strings (LSB). Add them plus any carry from the previous column.
2. Result digit = sum % 10, carry = sum / 10.
3. Handle unequal string lengths by treating missing digits as 0 — use the condition i >= 0 / j >= 0 to guard each access.
4. The while loop continues as long as any of the three conditions hold: digits left in num1, digits left in num2, or carry remaining.
5. Build the result string in reverse, then reverse at the end.

Time Complexity: O(max(m, n)) — single pass through both strings. Space Complexity: O(1) extra — result string is the output.

class Solution {
public:
    string addStrings(string num1, string num2) {
        string result;
        int carry = 0;
        int i = num1.size() - 1, j = num2.size() - 1;
        while (i >= 0 || j >= 0 || carry) {
            int sum = carry;
            if (i >= 0) sum += num1[i--] - '0';
            if (j >= 0) sum += num2[j--] - '0';
            result.push_back(sum % 10 + '0');
            carry = sum / 10;
        }
        reverse(result.begin(), result.end());
        return result;
    }
};

Embedded relevance: String-based arithmetic is used in embedded systems for BCD (Binary-Coded Decimal) display drivers and for handling high-precision sensor readings that exceed native integer width.

Key Insight: At each character position, you either have one choice (digit — no branching) or two choices (letter — lowercase or uppercase). This creates a binary decision tree where only letter positions branch. The total results is 2^k where k = number of letters.

Thought Process:

1. This is a branching/backtracking problem. At each position, decide what to do:
   • Digit: only one option, just continue.
   • Letter: two options (lower/upper), try both.
2. Backtracking with in-place modification: instead of creating new strings at each level, modify s[i] in place, recurse, then change to the other case and recurse again.
3. The in-place approach avoids O(n) string copies per recursive call — important for embedded contexts where memory allocation is expensive.
4. Alternative: bitmask enumeration (like Subsets). Assign each letter a bit; each mask value determines the case of each letter.

Time Complexity: O(n * 2^k) where k = number of letters in s. Space Complexity: O(n * 2^k) for storing all permutations (plus O(n) recursion stack).

class Solution {
public:
    vector<string> letterCasePermutation(string s) {
        vector<string> result;
        backtrack(s, 0, result);
        return result;
    }
private:
    void backtrack(string& s, int i, vector<string>& result) {
        if (i == (int)s.size()) {
            result.push_back(s);
            return;
        }
        if (isdigit(s[i])) {
            backtrack(s, i + 1, result);
        } else {
            s[i] = tolower(s[i]);
            backtrack(s, i + 1, result);
            s[i] = toupper(s[i]);
            backtrack(s, i + 1, result);
        }
    }
};

Embedded relevance: Case-insensitive command parsing in AT command handlers uses tolower/toupper on each character — this problem tests fluency with character classification and case conversion without locale dependencies.