Problem Description

Alice is trying to type a string on her computer, but she's clumsy and might accidentally hold a key down too long, causing a character to be typed multiple times in a row. She's careful enough that this mistake happens at most once while typing.

You're given a string word that represents what actually appeared on Alice's screen after she finished typing.

Your task is to find how many different original strings Alice could have been trying to type.

For example, if the screen shows "aabbcc", Alice might have been trying to type:

• "abbcc" (held 'a' too long)
• "aabcc" (held 'b' too long)
• "aabbc" (held 'c' too long)
• "aabbcc" (no mistakes)

The key insight is that when consecutive identical characters appear in the final string, they could either be intentional or the result of Alice's single typing mistake. Since she makes at most one mistake, we need to count all possibilities where:

1. She made no mistakes (the original string is exactly what we see)
2. She made one mistake at any position where consecutive identical characters appear

The solution counts pairs of adjacent identical characters. If there are k such pairs, then there are k + 1 possible original strings (including the case with no mistakes).

Intuition

Let's think about what happens when Alice makes a typing mistake. If she holds a key too long, it creates consecutive identical characters in the output. The crucial observation is that we can only "undo" one such mistake.

Consider the string "aabbcc". Where could Alice's single mistake have occurred?

• If she held 'a' too long: original was "abbcc"
• If she held 'b' too long: original was "aabcc"
• If she held 'c' too long: original was "aabbc"
• If she made no mistake: original was "aabbcc"

Notice that each pair of consecutive identical characters represents a potential location where the mistake could have happened. We can choose to "collapse" any one of these pairs back to a single character, or choose not to collapse any at all.

The key insight is that each pair of adjacent identical characters gives us exactly one additional possibility. Why? Because for each such pair, we have the choice of whether this was the location of Alice's single mistake.

If we have:

• 0 pairs of identical adjacent characters → only 1 possibility (no mistake possible)
• 1 pair of identical adjacent characters → 2 possibilities (mistake here or no mistake)
• 2 pairs of identical adjacent characters → 3 possibilities (mistake at first pair, second pair, or no mistake)
• k pairs of identical adjacent characters → k + 1 possibilities

This leads us directly to the solution: count the number of adjacent identical character pairs and add 1. The formula becomes 1 + count(adjacent identical pairs).

Solution Approach

The implementation is straightforward once we understand that we need to count pairs of adjacent identical characters.

The solution uses Python's pairwise function to iterate through consecutive character pairs in the string. For each pair (x, y), we check if x == y (characters are identical).

Here's how the algorithm works:

1. Iterate through adjacent pairs: Using pairwise(word), we get tuples of consecutive characters. For example, if word = "aabbcc", we get pairs: ('a','a'), ('a','b'), ('b','b'), ('b','c'), ('c','c').

2. Count identical pairs: For each pair (x, y), we check if x == y. This gives us a boolean that Python converts to 1 (True) or 0 (False). The expression sum(x == y for x, y in pairwise(word)) counts how many pairs have identical characters.

3. Add 1 for the base case: We add 1 to account for the possibility that Alice made no mistakes at all.

The complete solution in one line:

return 1 + sum(x == y for x, y in pairwise(word))

Time Complexity: O(n) where n is the length of the string, as we traverse it once.

Space Complexity: O(1) as we only use a constant amount of extra space (the pairwise iterator generates pairs on-the-fly).

For the example "aabbcc":

• Pairs: ('a','a'), ('a','b'), ('b','b'), ('b','c'), ('c','c')
• Identical pairs: ('a','a'), ('b','b'), ('c','c') → count = 3
• Result: 1 + 3 = 4 possible original strings

Example Walkthrough

Let's walk through the solution with the string "aabbcc":

Step 1: Identify all adjacent character pairs Using pairwise("aabbcc"), we get:

• Position 0-1: ('a', 'a') ✓ identical
• Position 1-2: ('a', 'b') ✗ different
• Position 2-3: ('b', 'b') ✓ identical
• Position 3-4: ('b', 'c') ✗ different
• Position 4-5: ('c', 'c') ✓ identical

Step 2: Count identical pairs We found 3 identical pairs: ('a','a'), ('b','b'), ('c','c')

Step 3: Calculate total possibilities Total = 1 (no mistake) + 3 (number of identical pairs) = 4 possible strings

Step 4: Verify our answer The 4 possible original strings Alice could have typed are:

1. "abbcc" - if she held 'a' too long (collapse first 'aa' pair)
2. "aabcc" - if she held 'b' too long (collapse 'bb' pair)
3. "aabbc" - if she held 'c' too long (collapse 'cc' pair)
4. "aabbcc" - if she made no mistake (keep all characters)

Let's trace through another example: "hello"

Step 1: Identify adjacent pairs

• ('h', 'e') ✗ different
• ('e', 'l') ✗ different
• ('l', 'l') ✓ identical
• ('l', 'o') ✗ different

Step 2: Count identical pairs Only 1 identical pair: ('l','l')

Step 3: Calculate total Total = 1 + 1 = 2 possible strings

The 2 possibilities are:

1. "helo" - if she held 'l' too long
2. "hello" - if she made no mistake

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the string. The algorithm iterates through the string once using pairwise(), which creates pairs of consecutive elements. For each pair, it performs a constant-time comparison (x == y). Since there are n-1 pairs for a string of length n, and each comparison takes O(1) time, the overall time complexity is O(n).

The space complexity is O(1). The pairwise() function generates pairs on-the-fly without storing all pairs in memory, using an iterator approach. The sum() function accumulates the result using a single variable to keep track of the count. No additional data structures that scale with input size are created, resulting in constant space usage.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Misunderstanding the Problem Scope

A common mistake is thinking that Alice could make multiple typing errors or that a "mistake" means typing the wrong character entirely. The problem specifically states she makes at most one mistake of holding a key too long, creating consecutive duplicates.

Wrong interpretation:

# Incorrectly trying to handle multiple mistakes or character substitutions
def wrongApproach(word):
    # This might try to count all possible compressions
    count = 0
    for i in range(len(word)):
        for j in range(i+1, len(word)+1):
            # Complex logic for multiple removals
            ...

Correct understanding: Count only the positions where a single consecutive character group could be reduced.

2. Off-by-One Error in Base Count

Developers often forget to include the original string (no mistakes) in the count, or accidentally double-count it.

Wrong:

def possibleStringCount(word):
    # Only counts the mistake positions, forgets the original
    return sum(word[i] == word[i+1] for i in range(len(word)-1))

Correct:

def possibleStringCount(word):
    # Adds 1 for the case where no mistake was made
    return 1 + sum(word[i] == word[i+1] for i in range(len(word)-1))

3. Handling Edge Cases Incorrectly

Failing to handle single-character strings or empty strings properly.

Wrong:

def possibleStringCount(word):
    # This crashes on empty string
    count = 1
    for i in range(len(word) - 1):  # range(-1) causes issues
        if word[i] == word[i + 1]:
            count += 1
    return count

Better approach with edge case handling:

def possibleStringCount(word):
    if len(word) <= 1:
        return 1  # Single char or empty has only one possibility
  
    count = 1
    for i in range(len(word) - 1):
        if word[i] == word[i + 1]:
            count += 1
    return count

4. Overthinking Group Sizes

Some might think they need to track the size of each consecutive character group and apply complex formulas.

Overcomplicated:

def possibleStringCount(word):
    groups = []
    current_group = 1
  
    for i in range(1, len(word)):
        if word[i] == word[i-1]:
            current_group += 1
        else:
            if current_group > 1:
                groups.append(current_group)
            current_group = 1
  
    # Complex calculation based on group sizes
    return sum(g for g in groups) + 1

Simple and correct: The number of adjacent pairs already gives us what we need - each pair represents one possible position where a mistake could have occurred.