Strings in DSA: Immutability, Character Codes and Patterns

A string is an array of characters with two twists that decide how you write almost every string solution. In most languages you cannot change a string once it exists, so building one carelessly is quadratic. And every character is really a small number, so a 26-slot array can count letters faster than any hash map. Get those two ideas right and most string problems become array problems you already know how to solve.

How a string is stored

A string keeps its characters contiguously, in order, with its length stored alongside, so s[i] and the length are O(1) and a walk from start to end is an ordinary O(n) pass. Each character is stored as a number, its code, and for the characters coding problems use the codes come from ASCII:

Beyond ASCII the languages differ — Java and JavaScript count UTF-16 units, Python whole characters, C++ bytes — which is why problems say "lowercase English letters". When any Unicode character is allowed, count with a hash map.

Immutability: which strings you can change

A C++ std::string is mutable: s[i] = 'x' changes a character in place and s += c appends in amortised O(1), like a vector. In Java, Python and JavaScript strings are immutable: anything that looks like an edit — s + c, replace, toUpperCase — builds a new string, and Python's s[0] = 'x' is an error.

That is deliberate: an immutable string can be shared safely, and is safe as a hash map key — a key that changed after being stored would sit in the wrong bucket. So edit something mutable and make the string once: a StringBuilder in Java, a list and one "".join(parts) in Python, an array and one parts.join("") in JavaScript.

The quadratic concatenation trap

Here is why that rule matters. result = result + c in a loop looks linear:

1. result = result + c builds a brand-new string every time, because Java, Python and JavaScript strings cannot change. Step 1 makes "a": 1 character copied.
2. Step 2 cannot extend "a" in place. It copies "a" into a new string and adds "b": 2 characters, and the old string is thrown away.
3. Step 3 copies all 2 old characters again, plus "c": 3 more, 6 so far. The copies pile up as a triangle.
4. Step 4 copies all 3 old characters again, plus "d": 4 more, 10 so far. The copies pile up as a triangle.
5. Step 5 copies all 4 old characters again, plus "e": 5 more, 15 so far. The copies pile up as a triangle.
6. Building n characters this way copies 1 + 2 + … + n = n(n + 1)/2 — 15 here, about 5 × 10⁹ for 100,000. A builder writes into spare room and converts once: 5 writes, O(n).

A builder avoids the triangle because it is a dynamic array of characters with spare capacity. Java's compiler merges a + b + c within one expression, but not across loop iterations; CPython and V8 sometimes soften the trap internally, but that can vanish, so write the builder.

Characters are numbers

Since characters are codes, much of string work is arithmetic:

Note the substring row: C++'s substr takes a start and a length, the others a start and an exclusive end.

Counting with a 26-slot array

Two strings are anagrams when they hold the same letters the same number of times, like "listen" and "silent" — the check in Valid Anagram. Sorting both works in O(n log n); counting is O(n). Add one per letter of the first string, subtract one per letter of the second, and check every slot is back to zero:

1. Only the letters that occur are drawn; the other 22 of the 26 slots stay 0. A letter's slot is c − 'a', so no hashing is needed, and the array's size never depends on the input: O(1) space.
2. Add s: 'r' − 'a' = 17, so slot 17 goes up by one.
3. 'a' − 'a' = 0: slot 0 goes up by one too.
4. 't' adds one to slot 19. The slots now hold how often each letter appears in "rat".
5. Now subtract t. 'c' never appeared in s, so its slot drops to −1: t has a letter s lacks.
6. 'a' takes one away from slot 0, which is back to 0.
7. 'r' takes one away from slot 17, which is back to 0.
8. Not anagrams: 'c' ends at −1 and 't' ends at 1. Strings are anagrams exactly when every slot ends at zero — one pass over each, O(n), against O(n log n) for sorting both.

An array beats a hash map here because c - 'a' is already an index: nothing to hash, nothing to collide. Once the alphabet is large or unknown, use Hashing.

#include <iostream>
#include <string>
using namespace std;

// True when t uses exactly the same letters as s, each the same number of times.
// Both strings hold lowercase English letters only.
bool isAnagram(const string& s, const string& t) {
    if (s.size() != t.size()) return false;
    int count[26] = {0};
    for (char c : s) count[c - 'a']++;       // 'a' -> 0, 'b' -> 1, ..., 'z' -> 25
    for (char c : t) count[c - 'a']--;
    for (int k = 0; k < 26; k++)
        if (count[k] != 0) return false;     // this letter appears more often in one string
    return true;
}

int main() {
    string pairs[3][2] = {{"listen", "silent"}, {"anagram", "nagaram"}, {"rat", "car"}};
    for (auto& p : pairs) {
        cout << p[0] << " / " << p[1] << ": " << (isAnagram(p[0], p[1]) ? "anagrams" : "not anagrams") << "\n";
    }
    return 0;
}

public class Main {
    // True when t uses exactly the same letters as s, each the same number of times.
    // Both strings hold lowercase English letters only.
    static 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']++;   // 'a' -> 0, ..., 'z' -> 25
        for (int i = 0; i < t.length(); i++) count[t.charAt(i) - 'a']--;
        for (int k = 0; k < 26; k++)
            if (count[k] != 0) return false;     // this letter appears more often in one string
        return true;
    }

    public static void main(String[] args) {
        String[][] pairs = {{"listen", "silent"}, {"anagram", "nagaram"}, {"rat", "car"}};
        for (String[] p : pairs) {
            System.out.println(p[0] + " / " + p[1] + ": " + (isAnagram(p[0], p[1]) ? "anagrams" : "not anagrams"));
        }
    }
}

def is_anagram(s, t):
    """True when t uses exactly the same letters as s, each the same number of times.
    Both strings hold lowercase English letters only."""
    if len(s) != len(t):
        return False
    count = [0] * 26
    for c in s:
        count[ord(c) - ord("a")] += 1       # 'a' -> 0, 'b' -> 1, ..., 'z' -> 25
    for c in t:
        count[ord(c) - ord("a")] -= 1
    for k in range(26):
        if count[k] != 0:                   # this letter appears more often in one string
            return False
    return True


pairs = [("listen", "silent"), ("anagram", "nagaram"), ("rat", "car")]
for s, t in pairs:
    print(f"{s} / {t}: {'anagrams' if is_anagram(s, t) else 'not anagrams'}")

// True when t uses exactly the same letters as s, each the same number of times.
// Both strings hold lowercase English letters only.
function isAnagram(s, t) {
  if (s.length !== t.length) return false;
  const A = "a".charCodeAt(0);
  const count = new Array(26).fill(0);
  for (let i = 0; i < s.length; i++) count[s.charCodeAt(i) - A]++; // 'a' -> 0, ..., 'z' -> 25
  for (let i = 0; i < t.length; i++) count[t.charCodeAt(i) - A]--;
  for (let k = 0; k < 26; k++) {
    if (count[k] !== 0) return false; // this letter appears more often in one string
  }
  return true;
}

const pairs = [
  ["listen", "silent"],
  ["anagram", "nagaram"],
  ["rat", "car"],
];
for (const [s, t] of pairs) {
  console.log(`${s} / ${t}: ${isAnagram(s, t) ? "anagrams" : "not anagrams"}`);
}

listen / silent: anagrams
anagram / nagaram: anagrams
rat / car: not anagrams

The same count answers many questions in one pass: Ransom Note checks that one string's counts cover another's, Find All Anagrams in a String slides a window of counts along a string, and First Unique Character in a String counts and then looks for the first count of 1.

Palindromes: compare from both ends

A palindrome reads the same both ways; Valid Palindrome also ignores case and anything that is not a letter or digit. A cleaned, reversed copy costs O(n) memory. Instead, walk a pointer in from each end:

• The left character is not a letter or digit: move left right.
• The right character is not a letter or digit: move right left.
• Both are: compare them in lower case. Different means false; equal means move both inwards.

This is the opposite-ends form of two pointers, with no copy at all.

1. Two pointers start at the two ends of "Don't nod." and walk inward. Anything that is not a letter or digit is skipped, and letters are compared in lower case, so spaces, punctuation and capitals cannot spoil the check.
2. The right pointer is on a full stop, which is not a letter or digit, so it steps left to index 8 without comparing anything.
3. 'D' and 'd' match once both are lower-cased to 'd', so this pair is fine — a single differing pair would end the check with false. Both pointers move inward, to 1 and 7.
4. 'o' and 'o' are the same letter, so this pair is fine. That makes 2 matching pairs; the pointers close in to 2 and 6.
5. 'n' and 'n' are the same letter, so this pair is fine. That makes 3 matching pairs; the pointers close in to 3 and 5.
6. The left pointer is on an apostrophe, which is not a letter or digit, so it steps right to index 4 without comparing anything.
7. The right pointer skips a space and lands on index 4, where the left pointer already is. The pointers have met, so every pair of letters has been checked.
8. "Don't nod." is a valid palindrome: its letters read d-o-n-t-n-o-d both ways. Each index is visited at most once by one pointer, so the check is O(n) time and O(1) space, with no cleaned copy of the string.

Why skipping is safe

Picture the cleaned string — letters and digits only, lower-cased. It is a palindrome when each character equals its mirror image, and skipping punctuation from both ends makes the pointers meet exactly those pairs, from the outside in:

1. Drop what is not a letter or digit and lower-case the rest: "Don't nod." becomes "dontnod", a palindrome when every mirror pair matches. Skipping punctuation from both ends makes the two pointers meet exactly these pairs, outermost first.
2. In "race a car" the first 3 pairs match, but pair 4, 'e' and 'a', does not, so the answer is false the moment the pointers reach it. Everything outside left..right is always already matched.

The invariant: every letter or digit outside left..right has matched its mirror image. It holds at the start, each step keeps it, and when the pointers meet every pair has matched. Neither pointer ever moves back, so the loop runs at most n times: O(n) time and O(1) extra space.

The code

#include <cctype>
#include <iostream>
#include <string>
using namespace std;

// True when s reads the same both ways, ignoring case and anything
// that is not a letter or a digit.
bool isPalindrome(const string& s) {
    int left = 0, right = (int)s.size() - 1;
    while (left < right) {
        if (!isalnum((unsigned char)s[left])) { left++; continue; }     // skip spaces and punctuation
        if (!isalnum((unsigned char)s[right])) { right--; continue; }
        if (tolower((unsigned char)s[left]) != tolower((unsigned char)s[right])) return false;
        left++;                                                         // this pair matches: move inwards
        right--;
    }
    return true;
}

int main() {
    string examples[] = {"Don't nod.", "A man, a plan, a canal: Panama", "race a car"};
    for (const string& s : examples) {
        cout << "\"" << s << "\": " << (isPalindrome(s) ? "palindrome" : "not a palindrome") << "\n";
    }
    return 0;
}

public class Main {
    // True when s reads the same both ways, ignoring case and anything
    // that is not a letter or a digit.
    static boolean isPalindrome(String s) {
        int left = 0, right = s.length() - 1;
        while (left < right) {
            if (!Character.isLetterOrDigit(s.charAt(left))) { left++; continue; }    // skip spaces and punctuation
            if (!Character.isLetterOrDigit(s.charAt(right))) { right--; continue; }
            if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) return false;
            left++;                                                                  // this pair matches: move inwards
            right--;
        }
        return true;
    }

    public static void main(String[] args) {
        String[] examples = {"Don't nod.", "A man, a plan, a canal: Panama", "race a car"};
        for (String s : examples) {
            System.out.println("\"" + s + "\": " + (isPalindrome(s) ? "palindrome" : "not a palindrome"));
        }
    }
}

def is_palindrome(s):
    """True when s reads the same both ways, ignoring case and anything
    that is not a letter or a digit."""
    left, right = 0, len(s) - 1
    while left < right:
        if not s[left].isalnum():        # skip spaces and punctuation
            left += 1
            continue
        if not s[right].isalnum():
            right -= 1
            continue
        if s[left].lower() != s[right].lower():
            return False
        left += 1                        # this pair matches: move inwards
        right -= 1
    return True


examples = ["Don't nod.", "A man, a plan, a canal: Panama", "race a car"]
for s in examples:
    verdict = "palindrome" if is_palindrome(s) else "not a palindrome"
    print(f'"{s}": {verdict}')

// True when s reads the same both ways, ignoring case and anything
// that is not a letter or a digit.
const isAlnum = (c) => /[a-z0-9]/i.test(c);

function isPalindrome(s) {
  let left = 0;
  let right = s.length - 1;
  while (left < right) {
    if (!isAlnum(s[left])) {
      left++; // skip spaces and punctuation
      continue;
    }
    if (!isAlnum(s[right])) {
      right--;
      continue;
    }
    if (s[left].toLowerCase() !== s[right].toLowerCase()) return false;
    left++; // this pair matches: move inwards
    right--;
  }
  return true;
}

const examples = ["Don't nod.", "A man, a plan, a canal: Panama", "race a car"];
for (const s of examples) {
  console.log(`"${s}": ${isPalindrome(s) ? "palindrome" : "not a palindrome"}`);
}

"Don't nod.": palindrome
"A man, a plan, a canal: Panama": palindrome
"race a car": not a palindrome

Valid Palindrome II allows one deletion: at the first mismatch, try skipping either character. Longest Palindromic Substring turns the check inside out and expands from each of the 2n − 1 centres, O(n²).

Building a new string: reversing the words

Many problems produce a new string, and this is where the builder rule pays off. Reverse Words in a String turns " the sky is blue " into "blue is sky the" in three O(n) steps:

1. The goal: the words in reverse order, separated by single spaces, with no spaces at the ends. The input has spaces at both ends and runs of several between words (drawn as dots).
2. Split, treating any run of spaces as one separator: 4 words, and every space is gone. Python's s.split() does this with no argument; Java and JavaScript trim, then split on runs of whitespace.
3. Reverse the list of words — the words themselves stay as they are. Splitting, reversing and joining are each one pass: O(n) in all.
4. Join once with single spaces: "blue is sky the". In Java, Python and JavaScript that one join (or a StringBuilder) is what keeps the build linear; a C++ std::string can simply append.

In C++, where strings are mutable, there is also an in-place version with O(1) extra space: reverse the whole string, reverse each word back, then squeeze out extra spaces with a write index. Reverse Words in a String III is the middle step on its own.

The code

The program prints each result between brackets, so stray spaces would show.

#include <algorithm>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
using namespace std;

// The words of s in reverse order, separated by single spaces.
string reverseWords(const string& s) {
    istringstream in(s);
    vector<string> words;
    string word;
    while (in >> word) words.push_back(word);       // >> skips any run of spaces
    reverse(words.begin(), words.end());
    string result;                                  // std::string is mutable: += is amortised O(1)
    for (const string& w : words) {
        if (!result.empty()) result += ' ';
        result += w;
    }
    return result;
}

int main() {
    string examples[] = {"  the sky   is blue  ", "a good   example"};
    for (const string& s : examples) cout << "[" << reverseWords(s) << "]\n";
    return 0;
}

import java.util.Arrays;
import java.util.Collections;

public class Main {
    // The words of s in reverse order, separated by single spaces.
    static String reverseWords(String s) {
        String[] words = s.trim().split("\\s+");        // split on runs of spaces
        Collections.reverse(Arrays.asList(words));      // reverses the array through a list view
        StringBuilder result = new StringBuilder();     // String is immutable: build with a StringBuilder
        for (String w : words) {
            if (result.length() > 0) result.append(' ');
            result.append(w);
        }
        return result.toString();
    }

    public static void main(String[] args) {
        String[] examples = {"  the sky   is blue  ", "a good   example"};
        for (String s : examples) System.out.println("[" + reverseWords(s) + "]");
    }
}

def reverse_words(s):
    """The words of s in reverse order, separated by single spaces."""
    words = s.split()                # no argument: splits on runs of spaces, drops empty pieces
    words.reverse()
    return " ".join(words)           # str is immutable: collect the pieces, join once


examples = ["  the sky   is blue  ", "a good   example"]
for s in examples:
    print(f"[{reverse_words(s)}]")

// The words of s in reverse order, separated by single spaces.
function reverseWords(s) {
  const words = s.trim().split(/\s+/); // split on runs of spaces
  words.reverse();
  return words.join(" "); // strings are immutable: collect the pieces, join once
}

const examples = ["  the sky   is blue  ", "a good   example"];
for (const s of examples) console.log(`[${reverseWords(s)}]`);

[blue is sky the]
[example good a]

Substrings, comparisons and other hidden costs

• Substrings copy. substr, substring, slicing and slice are O(k) for length k; copying all n(n + 1)/2 substrings is O(n³). Keep start and end indexes, or a C++17 string_view.
• Equality compares character by character: O(n), though different lengths are rejected at once.
• Ordering is by codes. "app" < "apple", and every capital sorts before every small letter: "Zebra" < "apple".
• Pattern search with find, indexOf or in can take O(n × m); KMP guarantees O(n + m) — see the string matching list.

Time and space complexity

How to recognise the pattern

• "Anagram", "permutation of", "can be formed from": counts, compared or subtracted.
• "Lowercase English letters" in the constraints: a 26-slot array instead of a hash map.
• "Palindrome": two pointers from both ends, or expanding from each centre.
• "Substring" with a condition: a sliding window.
• "Subsequence": two pointers across two strings, as in Is Subsequence, or dynamic programming.
• "Common prefix": compare column by column, as in Longest Common Prefix, or a trie for many queries.
• The answer is a new string: a builder, never repeated concatenation.

Common mistakes

• Concatenating in a loop. result += c on an immutable string is O(n²).
• Comparing Java strings with ==. It compares identity; use equals.
• Forgetting to normalise. "Racecar" is a palindrome only once case is ignored.
• Indexing the 26-slot array with a non-letter. 'A' - 'a' and ' ' - 'a' are negative; use 128 slots or a map.
• Character arithmetic surprises. In Java 'a' + 1 is the int 98; cast with (char). In C++, pass (unsigned char) c to isalnum and tolower.

Practice in this order

1. Reverse String: swap from both ends, in place.
2. Valid Anagram: the 26-slot count.
3. Valid Palindrome: skip, lower-case, compare from both ends.
4. Length of Last Word: scan from the end.
5. Longest Common Prefix: compare column by column.
6. Merge Strings Alternately: build with a builder.
7. Is Subsequence: one pointer in each string.
8. String Compression: read and write pointers, counts as digits.
9. Longest Palindromic Substring: expand around every centre.

Every string problem in the catalogue is on the string problem list. When the first six feel routine, move on to Two Pointers.