String Traversal

What Is String Traversal?

String traversal means visiting characters in a string one by one — or in a defined group — in a controlled order. It is the most fundamental string operation and the foundation of nearly every string algorithm you will write.

The character you are visiting might be checked against a condition, counted into a frequency table, compared to another character, or accumulated into a result. The traversal pattern you choose determines what information is available at each step and how efficiently the algorithm runs.

Strings share the same traversal mechanics as arrays — same index-based access, same loop structures, same boundary rules. But strings have two things arrays do not: built-in methods for word and line splitting, and character-level operations like isLetter(), isDigit(), and toLowerCase() that are used constantly in traversal logic.

Traversal 1: Forward Character Traversal (Index-Based)

The most common pattern. Visit every character from index 0 to length - 1 in order. Use this when you need the character's position — to compare it with a character at another index, to write back to a mutable buffer, or to track where a condition occurs.

Output (first few lines):
Characters and positions:
  [0] = 'H'
  [1] = 'e'
  [2] = 'l'
  [3] = 'l'
  [4] = 'o'
  [5] = ','
  [6] = ' '
  ...
Uppercase letters: 2

Traversal 2: For-Each Character Traversal

When you only need the character's value and do not need its position, a for-each loop is cleaner and eliminates off-by-one risk. Use this for summing, counting, or accumulating character values.

Output:
Vowel count: 3
Frequencies: {p:1, r:2, o:1, g:2, a:1, m:2, i:1, n:1}

Index-Based vs For-Each for Strings

Use index-based (for i = 0; i < s.length(); i++) when:
  - You need the position of a matching character
  - You need to look ahead:    s.charAt(i + 1)
  - You need to look behind:   s.charAt(i - 1)
  - You are comparing two positions in the same string
  - You need to fill a result array at the matching index
  - You are traversing two strings simultaneously

Use for-each when:
  - You only need character values
  - Position is irrelevant to the result
  - You are building a frequency map or sum
  - Cleaner, less error-prone code is preferred

Traversal 3: Backward Traversal

Traverse from the last character to the first. Use when the problem works naturally right-to-left — checking suffixes, finding the last occurrence, reversing, or comparing from the end.

Output:
Reversed: !dlroW ,olleH
Last vowel at index: 8 ('o')

Dry Run: Backward Traversal to Find Last Vowel in "Hello, World!"

String: "Hello, World!"
Index:   0123456789...

Backward scan starting at index 12:
  i=12: '!'  → not vowel → continue
  i=11: 'd'  → not vowel → continue
  i=10: 'l'  → not vowel → continue
  i=9:  'r'  → not vowel → continue
  i=8:  'o'  → IS vowel  → lastVowelIndex = 8, break

Result: index 8, character 'o'

Why backward? Scanning forward would find the first vowel.
Scanning backward and breaking at the first hit gives the last one.
O(n) worst case, O(1) best case — stops as soon as it finds the match.

Traversal 4: Two-Pointer Traversal

Two pointers — one at each end of the string — converge inward. This is the core technique for palindrome checking, string reversal validation, and any problem involving symmetric comparison of characters.

Output:
'racecar':              true
'hello':                false
'A man a plan a canal Panama': true
'':                     true
'a':                    true

Dry Run: Two-Pointer on "A man a plan a canal Panama"

Cleaned view (ignoring case and non-alphanumeric):
  amanaplanacanalpanama

Two pointers converge:
  L=0  R=19: 'a' == 'a' → match → L=1, R=18
  L=1  R=18: 'm' == 'm' → match → L=2, R=17
  L=2  R=17: 'a' == 'a' → match → L=3, R=16
  L=3  R=16: 'n' == 'n' → match → L=4, R=15
  ...
  All pairs match → return true

Key technique: the inner while loops skip spaces and punctuation
before comparing. This avoids pre-cleaning the string (O(n) extra space)
and handles all filtering inline during traversal — O(1) space.

Traversal 5: Sliding Window Over Characters

A fixed or variable-size window slides across the string, maintaining a running result. The window is defined by two indices — left and right — and slides by advancing the right index (expand) and the left index (shrink).

Output:
'eceba', k=2: 3
'aaaa',  k=1: 4
'abcde', k=3: 3

Dry Run: Sliding Window on "eceba", k=2

s = "eceba", k=2 (at most 2 distinct characters)

right=0: add 'e' → window="e",   freq={e:1}        distinct=1 ≤ 2 → maxLen=1
right=1: add 'c' → window="ec",  freq={e:1,c:1}    distinct=2 ≤ 2 → maxLen=2
right=2: add 'e' → window="ece", freq={e:2,c:1}    distinct=2 ≤ 2 → maxLen=3
right=3: add 'b' → window="eceb",freq={e:2,c:1,b:1}distinct=3 > 2 → SHRINK
  left=0: remove 'e' → freq={e:1,c:1,b:1} distinct=3 > 2 → continue
  left=1: remove 'c' → freq={e:1,b:1}     distinct=2 ≤ 2 → stop, left=2
  window="eb", right=3, maxLen=max(3, 3-2+1=2)=3
right=4: add 'a' → freq={e:1,b:1,a:1} distinct=3 > 2 → SHRINK
  left=2: remove 'e' → freq={b:1,a:1} distinct=2 ≤ 2 → stop, left=3
  window="ba", right=4, maxLen=max(3, 4-3+1=2)=3

Result: 3  (longest was "ece" at indices 0-2)

Traversal 6: Word-by-Word Traversal

Many string problems work at the word level, not the character level — counting words, reversing word order, checking if two strings are anagrams of each other word by word. Use split() to break the string into words, then traverse the resulting array.

Output:
Word count: 9
Longest word: jumps
Reversed words: dog lazy the over jumps fox brown quick The

Word count: 3
Longest word: spaces
Reversed words: here spaces extra

Traversal 7: Parallel String Traversal

Traverse two strings simultaneously with the same index. Use when comparing characters at the same position in two strings — checking if strings are equal, counting differences, or merging.

Output:
Hamming distance:
  'karolin' vs 'kathrin': 3
  'ACGT' vs 'TGCA':      4
Longest common prefix:
  'flower' vs 'flow':    flow
  'dog' vs 'racecar':    (empty)

Edge Cases Every String Traversal Must Handle

Empty String

Before any traversal that assumes content exists, check for empty input:

Empty string edge cases:
  s.length() == 0  → no characters → loop body never executes
  s.charAt(0)      → IndexOutOfBoundsException (Java)
  s[0]             → IndexError (Python) / undefined (JavaScript)
  s[0]             → undefined behavior (C++ — accessing past end)

Safe pattern:
  if (s.isEmpty()) return defaultValue;  // Handle before traversal
  // OR
  // Loop condition naturally handles it:
  for (int i = 0; i < s.length(); i++)  // Never executes if length == 0

Single Character

Most traversal algorithms work correctly on single-character strings without special handling — but verify:

Two-pointer on single char "a":
  left = 0, right = 0
  while (left < right) → false immediately → return true ✓

Backward traversal on single char:
  i = 0; i >= 0 → visits index 0 exactly once ✓

The Off-By-One Boundary in String Traversal

FORWARD traversal:
  Correct:   i < s.length()        → visits 0, 1, ..., n-1
  Wrong:     i <= s.length()       → crashes on s.charAt(n)

BACKWARD traversal:
  Correct:   i = s.length() - 1; i >= 0   → visits n-1, n-2, ..., 0
  Wrong:     i = s.length();     i >= 0   → crashes on s.charAt(n)

LOOK-AHEAD (checking s[i+1] when at index i):
  Correct:   i < s.length() - 1   → i+1 is always valid
  Wrong:     i < s.length()       → crashes when i == n-1 (i+1 == n)

LOOK-BEHIND (checking s[i-1] when at index i):
  Correct:   i > 0                → i-1 is always valid
  Wrong:     i >= 0               → crashes when i == 0 (i-1 == -1)

Traversal Pattern Summary

Interview Questions

Q: When should you use a for-each loop versus an index-based loop for string traversal?

Use for-each (range-based for in C++, for c in s in Python, for...of in JavaScript, for (char c : s.toCharArray()) in Java) when you only need character values and position is irrelevant — counting, summing, building a frequency map. Use an index-based loop when you need the character's position (to find where a match occurs), when you need to compare characters at different indices in the same string (palindrome check), or when you need to look ahead (s[i+1]) or look behind (s[i-1]).

Q: What is the time complexity of the two-pointer palindrome check?

O(n) time, O(1) space. Each pointer moves at most n/2 steps total — together they traverse the string once. The inner while loops that skip non-alphanumeric characters do not change this analysis because those pointers never move backward; each character is visited at most once by each pointer. No extra memory is allocated beyond the two index variables.

Q: How do you handle leading/trailing spaces when splitting a string into words?

Use trim() (Java/JavaScript) or strip() (Python) before splitting, or split with a pattern that handles multiple consecutive whitespace characters. In Java: s.trim().split("\\s+"). In Python: s.split() with no argument automatically handles all whitespace including leading/trailing. In JavaScript: s.trim().split(/\s+/). The key is that split(" ") on " hello world " produces empty strings ["", "", "hello", "", "world", "", ""] which then require filtering.

Q: How do you find the longest substring without repeating characters?

Use a sliding window with a hash set or hash map. Expand the right pointer adding each character. When a repeat is detected (character already in the set), shrink the left pointer until the repeat is removed. At each step, update the maximum window length. Time: O(n). Space: O(min(n, alphabet_size)) — the set holds at most as many entries as the alphabet has characters.

FAQs

In Python, can you iterate directly over a string without converting it?

Yes. Python strings are directly iterable — for c in s gives one character at a time without any conversion. This is different from Java, where you must call s.toCharArray() to use a for-each loop (or use s.charAt(i) in an indexed loop). Python's direct iteration is cleaner and does not create a copy.

Why does s.split("\\s+") in Java use a double backslash?

Because Java string literals use \ as an escape character. To pass the regex pattern \s+ (backslash-s-plus) to the regex engine, you write it as "\\s+" in a Java string literal — the \\ is the Java string representation of a single backslash, which the regex engine then interprets as \s. In Python, you write r'\s+' (raw string) or '\\s+' for the same regex.

When traversing with look-ahead (s[i+1]), how do you avoid crashing at the last index?

Either limit the loop to i < s.length() - 1 (so the last index is never reached inside the loop), or guard each look-ahead with if (i + 1 < s.length()) before accessing s[i+1]. The first approach is cleaner when you always need the look-ahead. The second is necessary when you conditionally look ahead depending on the current character.

Can you modify a string during traversal in any language?

In C++ you can modify std::string characters by index during traversal. In Java, Python, and JavaScript, strings are immutable — you cannot modify characters in place. Instead, convert to a mutable structure first: char[] chars = s.toCharArray() in Java, list(s) in Python, [...s] in JavaScript. Perform modifications on the mutable structure, then convert back to a string if needed.

Quick Quiz

Question 1: You want to find the index of the last occurrence of character 'x' in a string. Which traversal is most efficient?

• ›A) Forward traversal, record every matching index, return the last one
• ›B) Backward traversal, return the first matching index found
• ›C) For-each traversal using indexOf() repeatedly
• ›D) Two-pointer traversal

Answer: B) Backward traversal, return the first matching index found. Traversing from right to left, the first 'x' you encounter is the last one in the original string. Break immediately — O(1) best case. Forward traversal would need to scan the entire string even after finding early matches.

Question 2: In the sliding window for "longest substring without repeating characters," what is the space complexity?

• ›A) O(n) — you store the entire string
• ›B) O(1) — only two pointer variables
• ›C) O(min(n, k)) where k is the alphabet size
• ›D) O(n²) — all substrings are stored

Answer: C) O(min(n, k)). The hash set or frequency map stores the characters currently in the window. The window contains at most n characters, but each character must be unique (no repeats), so the set holds at most k entries where k is the alphabet size (26 for lowercase letters, 128 for ASCII). The set never grows larger than the number of distinct characters in the alphabet.

Question 3: "hello world".split() in Python returns:

• ›A) ['h', 'e', 'l', 'l', 'o', ' ', 'w', 'o', 'r', 'l', 'd']
• ›B) ['hello world']
• ›C) ['hello', 'world']
• ›D) ['hello', '', 'world']

Answer: C) ['hello', 'world']. Python's split() with no argument splits on any whitespace sequence and discards empty strings. It handles multiple consecutive spaces, tabs, and leading/trailing whitespace automatically. split(' ') (with a single space argument) would give ['hello', 'world'] here too, but would give ['', '', 'hello', '', 'world', '', ''] for " hello world ".

Question 4: What does the look-ahead guard i < s.length() - 1 protect against when accessing s.charAt(i + 1)?

• ›A) It prevents accessing a negative index
• ›B) It prevents accessing index s.length() which is out of bounds
• ›C) It prevents the loop from running on empty strings
• ›D) It ensures i + 1 is always even

Answer: B) It prevents accessing index s.length() which is out of bounds. When i == s.length() - 1 (the last valid index), i + 1 == s.length() — one past the end, which is out of bounds. The condition i < s.length() - 1 stops the loop before reaching the last index, ensuring i + 1 is always a valid index.

Summary

String traversal uses the same loop structures as array traversal but with string-specific character operations layered on top. The traversal pattern you choose determines what information is available at each step.

The key traversal patterns to carry forward:

• ›Forward index-based — when position, look-ahead/behind, or parallel comparison is needed
• ›Forward for-each — when only character values matter, cleaner and safer
• ›Backward — to find the last occurrence, process from right to left, or check suffixes
• ›Two-pointer converging — palindrome check, symmetric comparison, O(1) space
• ›Sliding window — longest or shortest substring with a validity condition, O(n) time
• ›Word-by-word — sentence-level problems, use split() then traverse the word array
• ›Parallel — comparing or merging two strings character by character

Always guard against two boundary conditions: empty strings (loop body never executes but pre-loop assumptions may crash) and off-by-one errors at the boundaries (accessing s[length] or s[i+1] at the last index).

In the next topic, you will explore String Operations — split, join, replace, trim, indexOf, and the other built-in methods that appear constantly in interview problems, with their true time complexities.