3330. Find the Original Typed String I

3330. Find the Original Typed String I

Difficulty: Easy

Topics: String

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.

Example 1:

• 
  Input: word = "abbcccc"


• 
  Output: 5


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

Example 2:

• 
  Input: word = "abcd"


• 
  Output: 1


• 
  Explanation: The only possible string is "abcd".

Example 3:

• 
  Input: word = "aaaa"


• 
  Output: 4

Constraints:

• 1 <= word.length <= 100


• 
  word consists only of lowercase English letters.

Hint:

1. Any group of consecutive characters might have been the mistake.

Solution:

We need to determine the number of possible original strings Alice might have intended to type, given that she may have pressed a key for too long at most once, resulting in one or more duplicate characters in a contiguous run. The key insight is that each contiguous run of characters in the input string could be the source of the mistake, and for each run of length L, there are L-1 possible original strings (since the original run could have been of any length from 1 to L-1). Additionally, the original string without any mistake is also a possibility.

Approach

1. 
   

   Problem Analysis: The problem involves analyzing the input string to identify contiguous runs of the same character. For each such run, if its length is L, Alice could have intended the run to be of any length from 1 to L-1 (since pressing a key too long would extend the run by at least one character). The total number of possible original strings is the sum of:

   
   
   
   
   
   • The original string itself (1 possibility).
   
   
   • For each run of length L, L-1 possibilities where one or more extra characters from that run are removed (leaving at least one character in the run).
   
   
   
   



2. Algorithm Selection: The algorithm involves traversing the string to break it into contiguous runs of the same character. For each run, the number of possibilities contributed is L-1, where L is the length of the run. The total number of original strings is then 1 + sum(L-1 for all runs).




3. Complexity Analysis: The algorithm processes each character in the string exactly once, making the time complexity O(n), where n is the length of the string. The space complexity is O(1) as no additional data structures are used beyond simple variables.

Let's implement this solution in PHP: a star on GitHub or sharing the post on your favorite social networks 😍.