String processing I (counting runs and building)

Strings are sequences of characters. You can iterate through them one character at a time, checking each one, counting how many match a pattern, or building a new string as you go. This is string processing.

Iterating through a string

A string is just a sequence. You can loop through it using the index of each character, or iterate over the characters directly.

s = "hello"for i in range(len(s)):    print(s[i])

This prints each character on its own line: h, e, l, l, o. The variable i goes from 0 to 4 (the length minus one). s[i] gives the character at position i.

You can also use a simpler for loop that does not need indices:

s = "hello"for char in s:    print(char)

This does the same thing. The variable char is the character at each position. Both approaches work. Use indices when you need to compare a character to the next one, since only an index lets you write s[i + 1]. Use direct iteration when you only need each character on its own, with no need to look ahead or behind. Run counting needs indices, because it constantly asks "is the next character the same as this one?"

Counting runs

A run is a sequence of identical characters. In the string "aabbcc", there are three runs: "aa", "bb", and "cc". Each run has length 2.

To count the length of a run, you start with a run counter at 1, then look ahead. If the next character matches the current one, add one to the counter and move on. When you find a character that is different, the run has ended.

1s = "aabbcc"2i = 03
4while i < len(s):5    current_char = s[i]6    count = 17    8    while i + count < len(s) and s[i + count] == current_char:9        count += 110    11    print(current_char, count)12    i += count

This program prints each character and its run length. For "aabbcc", it prints:

a 2b 2c 2

The outer loop advances by the length of each run. The inner loop counts how many consecutive characters match the current one. When the inner loop exits, count holds the length of the run.

1s = input()2result = ""3i = 04
5while i < len(s):6    current_char = s[i]7    count = 18
9    while i + count < len(s) and s[i + count] == current_char:10        count += 111
12    result += str(count) + current_char13    i += count14
15print(result)

aabbcc

2a2b2c

Building strings

You can build a new string by starting with an empty string and appending characters one at a time.

1result = ""2result += "a"3result += "b"4print(result)

This prints "ab". The += operator appends to the string. Each time you add to it, the string grows.

You can also build a string inside a loop:

1s = "aabbcc"2result = ""3
4for char in s:5    if char == "a":6        result += "X"7
8print(result)

This replaces every "a" with "X", producing "XXbbcc". The loop checks each character, and if it matches, appends a different character to the result.

A common use is to copy a string while transforming it:

1s = "hello"2result = ""3
4for char in s:5    result += char.upper()6
7print(result)

This converts the string to uppercase: "HELLO".

Combining: compress and build

Run-length encoding compresses a string by replacing each run with the run length and the character. The string "aabbcc" becomes "2a2b2c".

This combines counting runs and building a string. You iterate through the input, count each run, and append the count and character to the result.

1s = "aabbcc"2result = ""3i = 04
5while i < len(s):6    current_char = s[i]7    count = 18    9    while i + count < len(s) and s[i + count] == current_char:10        count += 111    12    result += str(count) + current_char13    i += count14
15print(result)

The key steps are: find the run, count it, convert the count to a string with str(count), append both to the result, and skip past the run you just processed with i += count.

Trace it on "aabbcc". At i = 0, current_char is "a". The inner loop looks at s[1], also "a", and raises count to 2. It then looks at s[2], which is "b", so the inner loop stops with count = 2. The program appends "2" and "a" to result, giving "2a", and moves i to 2. The same steps repeat for the run of "b" starting at index 2, appending "2b", and again for the run of "c" starting at index 4, appending "2c". By the time i reaches 6, the loop condition i < len(s) is false, and result holds "2a2b2c".

Two edge cases are worth checking by hand before you trust this pattern in a contest. An empty string never enters the while loop at all, since 0 < len(s) is false when s is empty, so result stays "". A string of one character, such as "z", forms a single run. At count = 1, the inner loop's condition i + count < len(s) is false, because there is no index 1 to look at in a string of length 1. The run ends immediately at length 1, and the output is "1z".

Common mistakes

The bounds check is easy to skip. When you compare s[i + count] to the current character, you must first check that i + count is still inside the string. Write i + count < len(s) before the comparison, in that order, or Python raises an IndexError once the run reaches the end of the string.

Another mistake is trying to modify the string in place. Strings in Python are immutable, so there is no way to change one character of an existing string. Build a new string with += instead.

A third mistake is forgetting to advance the index past the run you just counted. After you count a run, skip it with i += count. If the outer loop still advances by one instead, it processes the same run again on the next iteration and the counts come out wrong.

A fourth is comparing the wrong characters when looking ahead. Use s[i + count] to check the next character, not s[i] again. The character you already know is at s[i]; s[i + count] is the one you have not looked at yet.