Searching and Filtering Strings

A correct traversal visits every character exactly once, in order, and stops when it reaches the end of the string.

Programming

A Character-by-Character Walk

When you search or filter a string, you often need to examine its characters in order. Traversal is the process of handling a string one character at a time, from beginning to end. The index tells you which character is being handled, while the loop controls when the walk begins, continues, and ends.

Key point

A correct traversal visits every character exactly once, in order, and stops when it reaches the end of the string.

Which character does each index point to, and how does the index move from the first character to the last?

The Three-Part Loop

A while-loop traversal has three essential parts. First, an index variable starts at 0, which points to the first character. Second, the loop condition checks whether the index is still within the string. Third, the index increases by 1 after the current character is processed. These parts work together: the index identifies the current position, the condition protects the boundary, and the increment moves the traversal forward.

Code walkthrough

fruit = "banana"
index = 0

while index < len(fruit):
    print(fruit[index])
    index = index + 1

1
index = 0 selects the first character.
2
The condition checks that the index is less than len(fruit).
3
fruit[index] accesses the current character.
4
The character is printed.
5
index = index + 1 moves to the next position before the next condition check.

The string is named fruit.
The index begins at 0, the first valid position.
The loop continues while index is less than the string length.
fruit[index] retrieves the character at the current position.
The index increases by 1 after the character is processed.

What happens at each loop iteration as the index is checked, the current character is visited, and the index is incremented?

Tracing Banana

Worked example

Walking Through banana

Determine the characters visited by the traversal and the value of index when the loop stops.

1
Start
The string banana has length 6. The index starts at 0.
2
First iteration
The condition 0 < 6 is true. Index 0 selects b, and the index becomes 1.
3
Continuing iterations
Indices 1, 2, 3, 4, and 5 select a, n, a, n, and a in that order. After each character, the index increases by 1.
4
Final check
After index 5 is processed, the index becomes 6. The condition 6 < 6 is false, so the loop stops.

Result

The characters are visited in the order b, a, n, a, n, a. The loop stops when index is 6.

Output

b
a
n
a
n
a

In what order are characters processed, and how does each iteration contribute to the final output?

What do you think happens?

After the loop prints the character at index 5 in banana, what happens next?

The loop visits another character at index 6.
The index becomes 6 and the condition becomes false.
The index returns to 0.
The loop keeps printing the character at index 5.

Reveal answer

Answer:

The index becomes 6 and the condition becomes false.

banana has length 6. Its valid indices are 0 through 5. Once index becomes 6, index < len(fruit) is false, so the loop stops.

The Boundary Gate

The condition index < len(fruit) is the boundary check that keeps the traversal inside the string. If a string has length 5, its valid indices are 0, 1, 2, 3, and 4. The index value 5 is the string's length, not a valid character position. Therefore, the last character is accessed at len(fruit) - 1, and the loop should stop before trying to access the length itself.

What changes when the loop uses the wrong boundary, and which position becomes invalid?

Searching and Filtering Actions

Traversal supplies the repeated movement through the string. At each index, fruit[index] gives the current character, which can then be handled by the action your task requires. For a search, the action can inspect the current character to determine whether it is the character of interest. For filtering, the action can decide whether the current character should be retained or ignored. The traversal pattern remains the same: start at 0, check the boundary, process the current character, and increment the index.

How does each character move through a test that determines whether it is found, retained, or ignored?

Traversal Debugging

Common mistake
Starting the index at the wrong position
What it looks like
```
index = 1
```
Why it fails
The traversal pattern starts at 0 so that it begins with the first character. Starting at 1 skips the character at index 0.
Do this instead
Set index = 0 before the loop.
Common mistake
Using the wrong stopping condition
What it looks like
```
while index <= len(fruit):
```
Why it fails
When index reaches the string's length, that position does not contain a character. Including it attempts to access an index that does not exist.
Do this instead
```
Use while index < len(fruit):
```
Common mistake
Forgetting to increment the index
What it looks like
The loop processes fruit[index] but never changes index.
Why it fails
The index must move forward after each iteration so the traversal can reach the next character and eventually stop.
Do this instead
Increment the index by 1 after processing the current character.
Common mistake
Reading the index update as happening before the current character
What it looks like
```
index = index + 1 is treated as if it runs before fruit[index].
```
Why it fails
In the traversal pattern, the current character is accessed and processed before the index is incremented.
Do this instead
Trace each iteration in this order: check the condition, access the character, process it, then increment the index.

Before

index = 0
while index < len(fruit):
    print(fruit[index])
    index = index + 1

The condition stops when index reaches the string length.

After

index = 0
while index <= len(fruit):
    print(fruit[index])
    index = index + 1

The condition allows index to reach the string length, which is not a valid character position.

Practice Trace

EASY

Trace the traversal for the string banana. Write down the value of index and the character accessed on each iteration. Then identify the value of index at the first condition check that is false.

Hints

The string length is 6.
Begin with index 0.
The valid indices end at 5.
The index increases after each character is processed.

Your attempt (not saved)

Worked example

Practice Check

What index values access characters in banana, and what value stops the loop?

1
Character positions
The character positions are 0, 1, 2, 3, 4, and 5.
2
Character order
Those positions access b, a, n, a, n, and a.
3
Stopping value
After index 5 is processed, the index becomes 6. The condition 6 < 6 is false.

Result

The loop accesses indices 0 through 5 and stops with index equal to 6.

Key Takeaways

1
Traversal handles a string one character at a time from beginning to end.
2
The standard while-loop pattern starts index at 0, checks index < len(string), processes string[index], and increments index by 1.
3
For a string of length 6, valid indices are 0 through 5; index 6 signals that traversal should stop.
4
The condition index < len(string) prevents the loop from accessing a position that does not exist.
5
Searching and filtering actions can be placed inside the traversal after the current character is accessed.

At a glance

Traversal means processing a string one character at a time in order.
A while loop needs an index, a boundary condition, and an increment.
The last valid index is len(string) - 1, so the loop condition should use a strict less-than comparison.
Tracing the index before and after each iteration reveals skipped characters, invalid accesses, and missing increments.
Searching and filtering actions can use the current character produced by the traversal.

Related concepts

More concepts starting with S