#3330

Easy

auto_awesomeString-driven solution strategy

LeetCode Problem Workspace

Find the Original Typed String I

Determine the length of the original string Alice intended to type by analyzing repeated characters and clumsy key presses.

string

Problem Statement

Alice is trying to type a string on her computer, but she may accidentally press a key too long, causing repeated characters. Given the final string displayed, determine the maximum length of the original string she intended to type before any accidental repetition.

You are given a string word containing only lowercase letters. Assume Alice may have made at most one accidental repeat in any group of consecutive identical characters. Return the total number of valid original strings that could have produced the displayed word.

Examples

Example 1

Input: word = "abbcccc"

Output: 5

The possible strings are: "abbcccc" , "abbccc" , "abbcc" , "abbc" , and "abcccc" .

Example 2

Input: word = "abcd"

Output: 1

The only possible string is "abcd" .

Example 3

Input: word = "aaaa"

Output: 4

Example details omitted.

Constraints

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

Solution Approach

Scan consecutive character groups

Iterate through the string word and identify consecutive identical characters. Count each group and consider that one character might be the intended input while the rest could be accidental repeats.

Accumulate possible original lengths

For each consecutive group, add its length to a total counter, but subtract one if you assume the extra occurrences are due to a clumsy key press. This captures the string-driven pattern central to this problem.

Return final count

After processing all character groups, the accumulated total represents the maximum possible length of the original typed string. This approach guarantees O(n) time and O(1) space.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(1)

The solution scans the input string once, processing each character exactly once, resulting in O(n) time complexity. Only a fixed number of variables are used for counters and indices, making the space complexity O(1).

What Interviewers Usually Probe

Notice patterns of consecutive repeated letters to test the candidate's string analysis skills.
Ask why simply counting characters may overestimate the original length if repeated presses occur.
Look for recognition that at most one accidental repetition per group affects the valid original count.

Common Pitfalls or Variants

Common pitfalls

Assuming all repeated characters are intentional, which overcounts the original string length.
Failing to handle single-character groups correctly, leading to off-by-one errors.
Using extra data structures unnecessarily, increasing space complexity beyond O(1).

Follow-up variants

Allow multiple accidental repeats per character group instead of at most one.
Determine the minimum possible length of the original string instead of the maximum.
Extend the problem to uppercase letters or digits to test general string handling.

FAQ

What does the term 'original typed string' mean in this problem?

It refers to the string Alice intended to type before any accidental repeated keystrokes occurred.

Can Alice make more than one accidental repeat in a character group?

No, the problem assumes at most one accidental repetition per consecutive character group.

Is it necessary to use extra space for storing character counts?

No, the solution can be implemented with O(1) extra space using simple counters and indices.

How does the string-driven solution strategy apply here?

It focuses on analyzing consecutive character sequences to determine the intended original string length efficiently.

What is the expected output for word = 'abbcccc'?

The maximum length of the original string is 5, considering possible clumsy repeats in character groups.

terminal

Solution

Solution 1: Direct Traversal

According to the problem description, if all adjacent characters are different, there is only 1 possible original input string. If there is 1 pair of adjacent identical characters, such as "abbc", then there are 2 possible original strings: "abc" and "abbc".

1

2

3

class Solution:
    def possibleStringCount(self, word: str) -> int:
        return 1 + sum(x == y for x, y in pairwise(word))

Continue Practicing

#3331 find subtree sizes after changes #3327 check if dfs strings are palindromes #3333 find the original typed string ii