Find the Original Typed String I

Find the Original Typed String I

1. What is this problem about?

The Find the Original Typed String I interview question is a string simulation and counting problem. You are given a string typed that was supposedly typed by a user. However, some keys might have been pressed for too long, causing characters to be repeated. Your goal is to find the total number of distinct "original" strings that could have resulted in the typed string, assuming the only error was character repetition.

2. Why is this asked in interviews?

Companies like Microsoft and Amazon ask the Find the Original Typed String I coding problem to assess a candidate's basic string manipulation and counting logic. It tests your ability to identify "clusters" of identical characters and understand how variations in those clusters affect the total number of possible original strings. It evaluations your grasp of linear scanning and basic combinatorics within a String interview pattern.

3. Algorithmic pattern used

This problem follows the Linear Scan and Counting pattern.

• Group Identical Characters: Iterate through the string and find contiguous blocks of the same character.
• Counting Rule: For a block of $K$ identical characters (e.g., "aaaa"), the user could have intended to type any number of 'a's from 1 to $K$.
• Wait, refinement: In many versions of this problem, the rule is simpler: you only need to count how many extra characters were added. The number of original strings is the product of the lengths of all identical groups, or simply related to the sum of "extra" choices available at each group.

4. Example explanation

Suppose typed = "aabb".

• Groups are: "aa" (length 2) and "bb" (length 2).
• At "aa", the user could have typed "a" or "aa".
• At "bb", the user could have typed "b" or "bb".
• Combinations: "ab", "abb", "aab", "aabb". Total possible original strings: 4. If the rule says the user definitely repeated keys, the question might ask for specific subsets, but the core is identifying block lengths.

5. Common mistakes candidates make

• Ignoring the relative order: Attempting to use a frequency map (Hash Table) for the whole string. This loses the contiguous "block" information which is vital.
• Off-by-one errors: Counting the number of transitions instead of the length of the blocks.
• Complexity: Using recursion or backtracking to generate all strings, which is $O(2^N)$ and unnecessary when only the count is required.

6. Interview preparation tip

Whenever a string problem involves "repeating characters," your first thought should be a Linear Scan to identify character clusters. This is a recurring theme in compression and data cleaning problems.