String Manipulation Techniques
String questions become simpler when classified by the state they need: two pointers for symmetric edits, counters for multiplicity, sliding windows for contiguous constraints, and stacks for nested structure.
Representation comes before technique
In Python, Java, and JavaScript, strings are immutable. An 'in-place' reversal therefore means operating on a mutable character array or returning a new string; repeatedly concatenating immutable strings inside a loop can create quadratic copying.
Characters are not always bytes. Unicode code points, grapheme clusters, normalization, and case folding matter when a problem means human-visible text. Interview problems often restrict input to ASCII or lowercase letters, but production code must state its unit explicitly.
- Know whether mutation is possible
- Avoid repeated immutable concatenation
- Define the character model
Two pointers for symmetry and compaction
Reversal swaps the left and right characters and moves inward, performing floor(N/2) swaps with O(1) extra space on a mutable array. Palindrome validation compares the same symmetric pairs and may skip characters that the problem declares irrelevant.
A slow/fast pair supports in-place filtering: fast scans every character and slow writes only retained characters. This is the string analogue of removing array elements without allocating another full buffer.
- Opposing pointers test symmetry
- Fast reads while slow writes
- State the filtering rules
Two-pointer palindrome check
s = "racecar"
left = 0
right = len(s) - 1
ok = True
while left < right:
if s[left] != s[right]:
ok = False
break
left += 1
right -= 1
print("Palindrome:", ok)#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <functional>
#include <tuple>
#include <array>
#include <numeric>
using namespace std;
int main()
{
string s="racecar";
bool ok=equal(s.begin(),s.begin()+s.size()/2,s.rbegin());
cout<<"Palindrome: "<<(ok?"True":"False");
}class Main
{
public static void main(String[]z)
{
String s="racecar";
boolean ok=true;
for(int l=0,r=s.length()-1;l<r;l++,r--)if(s.charAt(l)!=s.charAt(r))ok=false;
System.out.print("Palindrome: "+(ok?"True":"False"));
}
}mutable characters racecarPalindrome: TrueRun the example step by step
Frequency maps for anagrams
Two strings are anagrams when their symbol multiplicities match after any allowed normalization. A fixed-size frequency array is fastest for a known small alphabet; a hash map handles a large or unknown alphabet. Sorting is simpler but costs O(N log N).
Increment counts for the first string and decrement for the second, rejecting a negative count early or verifying all zeros at the end. Length equality is a cheap prerequisite when both strings use the same symbol unit.
- Anagrams compare multiplicity
- Arrays suit fixed alphabets
- Maps suit general symbols
Substrings, subsequences, and parsing
Contiguous substring constraints often call for a sliding window because characters enter and leave at boundaries. Subsequences preserve order but may skip positions, leading to two pointers or dynamic programming. Confusing the two produces algorithms that solve a different problem.
Nested delimiters and reversible operations often need a stack, while prefix lookup suggests a trie and exact pattern search suggests KMP or Rabin–Karp. Recognizing the required state is more valuable than memorizing dozens of isolated solutions.
- Substring means contiguous
- Subsequence permits gaps
- Nested structure suggests a stack
Edge cases and testing
Test empty input, one character, even and odd palindrome centers, repeated symbols, all-skipped punctuation, and non-ASCII input when permitted. For in-place edits, verify the returned logical length as well as the buffer prefix.
Do not lowercase or discard punctuation unless the specification authorizes normalization; doing so can silently change equality. State time in terms of processed code units and include any output allocation in the space analysis.
- Normalization changes semantics
- Test both palindrome center types
- Count output storage honestly
A decision process for interview problems
First identify whether order, multiplicity, contiguity, or nesting determines the answer. Symmetric order suggests opposing pointers; multiplicity suggests a counter; a contiguous constraint suggests a window; nested delimiters suggest a stack. Then write the invariant in one sentence before coding. This prevents an anagram solution from accidentally checking set membership, or a substring solution from accepting a subsequence.
Next choose representation and boundaries. Decide whether case, punctuation, normalization, and whitespace matter, and whether the output may allocate storage. Test empty and one-character input, repeated symbols, even and odd centers, characters outside ASCII, and cases where normalization changes the result. Complexity claims should count conversions such as building a character array or normalized copy, since those allocations are part of the algorithm users actually run.
For transformations, clarify whether preserving the original string is required and whether indexes in the answer refer to the original or normalized representation. That choice affects both correctness and the ability to map a result back to user-visible text.
- Classify the required state first
- Write the invariant before the loop
- Include normalization and copies in complexity