Problem Statement

Alice is attempting to type a specific string on her computer. However, she tends to be clumsy and may press a key for too long, resulting in a character being typed multiple times.

Although Alice tried to focus on her typing, she is aware that she may still have done this at most once.

You are given a string word, which represents the final output displayed on Alice's screen.

🔍Your task:

Return the total number of possible original strings that Alice might have intended to type.

LeetCode

Find the original types string 1

Constraints

• 1 <= word.length <= 100
• word consists only of lowercase English letters.

Examples

Example 1:

Input: word = "abbcccc"
Output: 5

Explanation: The possible strings are:
"abbcccc"
"abbccc"
"abbcc"
"abbc"
"abcccc"

Example 2:

Input: word = "abcd"
Output: 1

Explanation: The only possible string is:
"abcd", as all characters are unique she must
not have pressed key for long

Example 3:

Input: word: "aaaa"
Output: 4

Explanation: All possible string are:
"aaaa"
"aaa"
"aa"
"a"

Different Approaches

1️⃣ Iterate (Duplicate Group Check)

Intuition:

Only one group of consecutive repeated characters may be the result of long pressing.

In each such group (e.g., “cccc”), Alice might have meant:

• “c” (intended only one press)
• “cc” (intended two presses)
• …
• up to the full group (meaning no mistake)

So, if there are n repeated characters in a group, there are n possible original version if we assume that group is the mistake.

Approach:

1. We can have a count which would be initialized to 1 (for the entire string, as there could be no long typing).
2. Iterate over the array during that check for the previous element if both are equal then increment the count. If not then do nothing.

Code:

class Solution {
public:
    // This function returns the number of possible original strings
    // Alice could have intended to type, given the final 'word' she typed.
    int possibleStringCount(string word) {
        // Start with 1 because the original string might be correct (no mistake at all)
        int count = 1;

        // Loop through the string starting from the second character
        for(int i = 1; i < word.size(); i++) {
            // Check if the current character is the same as the previous one
            // This means a possible long key press occurred
            if (word[i - 1] == word[i]) {
                // Increase the count because we assume this could be the one mistake
                count++;
            }
        }

        // Return the total number of possible original strings
        return count;
    }
};

⏱️Complexity Analysis:

• 🕒Time Complexity:O(n)
  • The loop runs once through the string.
• 💾Space Complexity:O(1)
  • Constant space, no extra memory is used.