Strings in DSA — Palindromes, Reversals and Pattern Tricks

Strings are arrays of characters with a few special rules. Most string questions reuse ideas you already know — two pointers, counting with a map and sliding window — plus one or two string-specific tricks.

Strings are immutable (and why that matters)

In both Python and Java, a string cannot be changed in place. s = s + "a" creates a brand-new string and copies all the old characters. Do that inside a loop and your O(n) idea quietly becomes O(n²).

# Slow: O(n²) copying
out = ""
for ch in s:
    out += ch.upper()

# Fast: collect pieces, join once — O(n)
out = "".join(ch.upper() for ch in s)

// Fast in Java: StringBuilder is a mutable buffer
StringBuilder sb = new StringBuilder();
for (char ch : s.toCharArray()) sb.append(Character.toUpperCase(ch));
String out = sb.toString();

To edit characters in place, convert to a list (Python) or char array (Java) first.

Useful character facts

• ord('a') = 97 in Python; 'c' - 'a' = 2 in Java. Use ch - 'a' to map letters to indexes 0–25 for a count array.
• Check types: ch.isalnum(), ch.isdigit() (Python) / Character.isLetterOrDigit(ch) (Java).
• Comparing strings: == compares values in Python; in Java use s.equals(t) — == compares references.

Technique 1 — Two pointers (reverse, palindrome)

def reverse_string(chars):          # in place, O(1) extra space
    l, r = 0, len(chars) - 1
    while l < r:
        chars[l], chars[r] = chars[r], chars[l]
        l += 1
        r -= 1

A palindrome check is the same loop with a comparison instead of a swap.

Technique 2 — Split and rebuild (reverse words)

Reverse Words in a String: " the sky is blue " → "blue is sky the".

def reverse_words(s):
    return " ".join(reversed(s.split()))   # split() drops extra spaces

String reverseWords(String s) {
    String[] words = s.trim().split("\\s+");
    StringBuilder sb = new StringBuilder();
    for (int i = words.length - 1; i >= 0; i--) {
        sb.append(words[i]);
        if (i > 0) sb.append(' ');
    }
    return sb.toString();
}

Technique 3 — Compare position by position (longest common prefix)

def longest_common_prefix(strs):
    prefix = strs[0]
    for word in strs[1:]:
        while not word.startswith(prefix):
            prefix = prefix[:-1]          # shorten until it fits
            if not prefix:
                return ""
    return prefix

Technique 4 — Expand around center (palindromic substrings)

Every palindrome has a center: a single character ("aba") or a gap between two equal characters ("abba"). Try every center and expand outward while both ends match.

def longest_palindrome(s):
    best = ""
    for center in range(len(s)):
        for l, r in ((center, center), (center, center + 1)):   # odd and even length
            while l >= 0 and r < len(s) and s[l] == s[r]:
                l -= 1
                r += 1
            if r - l - 1 > len(best):
                best = s[l + 1:r]
    return best

There are 2n − 1 centers and each expansion is O(n) → O(n²) time, O(1) space. Counting all palindromic substrings is the same loop, adding 1 for each successful expansion.

Technique 5 — Parse carefully (String to Integer / atoi)

Questions like atoi test careful handling, not clever algorithms. Walk through the string with an index and handle each case in order: leading spaces → optional sign → digits → stop at the first non-digit → clamp to the 32-bit range. Write the cases down before you code.

Searching for a pattern

haystack.find(needle) (Python) / indexOf (Java) solve "find the first occurrence". A simple double loop is O(n·m), which is usually accepted in interviews. Advanced algorithms (KMP, Rabin–Karp) bring it to O(n + m) — worth learning later, rarely required for freshers.

How to recognise the technique

Question mentions…	Try
palindrome, reverse	two pointers
anagram, frequency, same characters	count array / hash map
longest substring with a condition	sliding window
longest palindromic substring	expand around center
parsing, conversion	careful step-by-step index walk

Common mistakes

1. String concatenation in a loop (O(n²)) — use join / StringBuilder.
2. Java: comparing strings with == instead of .equals().
3. Forgetting the even-length center in palindrome problems.
4. Not handling empty strings, spaces and case differences.

Key takeaways

• Strings are immutable: build with join / StringBuilder.
• Most string problems are array problems in disguise — two pointers, counting, sliding window.
• Palindromic substrings → expand around center, O(n²) time, O(1) space.