Find the Original Typed String I - Practice Coding Problems

Find the Original Typed String I - Problem

String Easy

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. Return the total number of possible original strings that Alice might have intended to type.

Input & Output

Example 1 — Multiple Groups

$ Input: word = "aabbaa"

› Output: 4

💡 Note: Three groups of consecutive duplicates: 'aa', 'bb', 'aa'. Each can be shortened by one character, plus the original string. Total: 1 + 3 = 4

Example 2 — Single Characters

$ Input: word = "abc"

› Output: 1

💡 Note: No consecutive duplicate characters, so only the original string 'abc' is possible

Example 3 — One Long Group

$ Input: word = "aaaa"

› Output: 2

💡 Note: One group of 4 consecutive 'a's can be shortened to 3 'a's, plus the original. Total: 1 + 1 = 2

Constraints

1 ≤ word.length ≤ 100
word consists of lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Alice's Output

The final typed string 'aabbaa' displayed on screen

Identify Mistakes

Find groups where Alice might have held keys too long

Count Possibilities

Each group adds one potential original string

Key Takeaway

🎯 Key Insight: Each consecutive duplicate group represents one potential typing mistake that can be 'undone'

Asked in

G Google 15 M Microsoft 12 a Amazon 8

The key insight is that each group of consecutive identical characters (length ≥ 2) represents exactly one possible place where Alice held a key too long. Best approach is to count these groups in O(n) time: answer = 1 + number_of_consecutive_groups. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Optimized - Count Consecutive Groups	O(n)	O(1)	Count consecutive identical character groups and add one for each group
Brute Force - Check All Substrings	O(n³)	O(n²)	Try removing every possible substring of consecutive identical characters

Optimized - Count Consecutive Groups — Algorithm Steps

Scan through the string once
Count groups of consecutive identical characters of length ≥ 2
Return original count + number of such groups

Visualization

Tap to expand

Step-by-Step Walkthrough

Scan Groups

Identify consecutive character groups in one pass

Count Valid Groups

Each group with 2+ characters adds one possibility

Calculate Total

Original + number of valid groups = answer

Code -

solution.c — C

#include <stdio.h>
#include <string.h>

int solution(char* word) {
    int len = strlen(word);
    if (len <= 1) {
        return 1;
    }
    
    int count = 1; // Original string is always possible
    int i = 0;
    
    while (i < len) {
        int j = i;
        // Find the end of current consecutive group
        while (j < len && word[j] == word[i]) {
            j++;
        }
        
        // If group has 2 or more characters, we can remove one
        if (j - i >= 2) {
            count++;
        }
        
        i = j;
    }
    
    return count;
}

int main() {
    char word[1000];
    fgets(word, sizeof(word), stdin);
    word[strcspn(word, "\n")] = 0; // Remove newline
    
    int result = solution(word);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through the string to identify consecutive groups

✓ Linear Growth

Space Complexity

O(1)

Only using a few variables to track current group

✓ Linear Space

8.5K Views

Medium Frequency

~15 min Avg. Time

420 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized - Count Consecutive Groups — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler