Strings — Manipulation and Patterns

Strings in Memory

A string is a sequence of characters stored as an array of bytes. In most languages, strings are immutable — operations like concatenation create new strings rather than modifying the original.

String s = "hello";
// Strings are immutable in Java
// s.charAt(0) = 'H'; // ❌ Compiler error
 
s = "H" + s.substring(1); // ✅ creates a new string "Hello"

Implication: Concatenating strings in a loop is O(n²) — use a StringBuilder instead.

// ❌ O(n²) — creates a new string each iteration
String result = "";
for (char c : chars) {
    result += c;
}
 
// ✅ O(n) — use StringBuilder
StringBuilder sb = new StringBuilder();
for (char c : chars) {
    sb.append(c);
}
String result = sb.toString();

Essential String Operations

Operation	Java	Time
Length	`s.length()`	O(1)
Access char	`s.charAt(i)`	O(1)
Substring	`s.substring(i, j)`	O(j-i)
Concatenate	`s1 + s2`	O(n)
Find substring	`s.indexOf(t)`	O(n·m)
Split	`s.split(" ")`	O(n)
Join	`String.join("", arr)`	O(n)
Reverse	`new StringBuilder(s).reverse().toString()`	O(n)
Lower/Upper	`s.toLowerCase()`	O(n)

Pattern 1 — Two Pointers

Use when checking palindromes, reversing, or comparing from both ends.

Valid Palindrome

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;

Reverse Words in a String

public 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();
}
 
// reverseWords("  hello world  ")  -> "world hello"

Pattern 2 — Sliding Window

Use for substrings with constraints — longest, shortest, with/without repeats.

Longest Substring Without Repeating Characters

public int lengthOfLongestSubstring(String s) {
    Map<Character, Integer> charIndex = new HashMap<>();
    int left = 0, maxLen = 0;
 
    for (int right = 0; right < s.length(); right++) {
        char ch = s.charAt(right);
        if (charIndex.containsKey(ch) && charIndex.get(ch) >= left) {
            left = charIndex.get(ch) + 1; // shrink window
        }
        charIndex.put(ch, right);
        maxLen =

Minimum Window Substring

public String minWindow(String s, String t) {
    if (s.length() == 0 || t.length() == 0) return "";
    int[] need = new int[128];
    for (char c : t.toCharArray()) need[c]++;
    
    int missing = t.length(), left = 0;
    int[] ans = {-1, 0, 0}; // length, left, right
 
    for (int right = 0; right < s.

Pattern 3 — Hashing / Frequency Count

Use for anagrams, character frequency problems.

Valid Anagram

public 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']++;
        count[t.charAt(i) - 'a']--;
    }
    for (int c : count) {
        if (c != 0) return false;
    }

Group Anagrams

import java.util.*;
 
public List<List<String>> groupAnagrams(String[] strs) {
    Map<String, List<String>> groups = new HashMap<>();
    for (String s : strs) {
        char[] chars = s.toCharArray();
        Arrays.sort(chars);
        String key = new String(chars); // canonical form
        groups.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
    }
    return new ArrayList<>(groups.values());
}

Pattern 4 — String Matching (KMP)

For finding a pattern in a string efficiently — O(n+m) instead of O(n·m).

public List<Integer> kmpSearch(String text, String pattern) {
    int m = pattern.length();
    int[] fail = new int[m];
    int j = 0;
    // Build failure function
    for (int i = 1; i < m; i++) {
        while (j > 0 && pattern.charAt(i) != pattern.charAt(j)) {
            j = fail[j - 1];
        }
        if (pattern.charAt(i) == pattern.charAt(j)) {
            j++;

Common Interview Problems

Problem	Pattern	Key insight
Valid palindrome	Two pointers	Skip non-alphanumeric
Longest substring no repeat	Sliding window + hash	Track last seen index
Minimum window substring	Sliding window	Shrink when valid
Group anagrams	Hashing	Sorted string as key
Valid anagram	Frequency count	26-char array
Longest palindromic substring	Expand around center	Check odd and even length
String compression	Two pointers	Count consecutive chars
Encode/decode strings	Delimiter encoding	Length-prefix protocol

Longest Palindromic Substring

public String longestPalindrome(String s) {
    if (s == null || s.length() < 1) return "";
    int start = 0, end = 0;
 
    for (int i = 0; i < s.length(); i++) {
        int len1 = expand(s, i, i);     // odd length: "aba"
        int len2 = expand(s, i, i + 1); // even length: "abba"
        int len = Math.max(len1, len2);
        if (len > end - start) {
            start =

Key Takeaway

Strings are immutable — use StringBuilder not += in loops
Two pointers — palindromes, reversal, comparison from both ends
Sliding window — longest/shortest substring with constraints
Hashing/Counter — anagrams, frequency problems
Always clarify: ASCII or Unicode? Case sensitive? What counts as a valid character?