Jobs

Interviews

Discussions

Find the Original Typed String I

Easy

Asked by:

5 views

Topics:

StringsTwo Pointers

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.

Try coding it in LeetCode

Find the Original Typed String I

Easy

Asked by:

5 views

Topics:

StringsTwo Pointers

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.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What should I return if it is not possible to form string `t` from string `s` by removing characters?
Are `s` and `t` guaranteed to be non-null or non-empty strings?
If there are multiple valid original typed strings that could form `t`, is any one acceptable, or is there a specific original typed string I should return (e.g., the lexicographically smallest)?
Are there any constraints on the characters that `s` and `t` can contain (e.g., only lowercase letters, ASCII characters)?
What are the maximum lengths of the strings `s` and `t`?

Brute Force Solution

Approach

The basic idea is to try out all possible ways to build the original string. We'll check each possibility to see if it matches the longer, typed-out string.

Here's how the algorithm would work step-by-step:

Start by assuming the first character of the typed string is from the original string.
Then, check if the rest of the typed string could have been created by accidentally adding extra characters after that first character.
Next, assume the first two characters of the typed string are from the original string.
Again, see if the remaining characters of the typed string could be the result of typos after those two characters.
Keep doing this, trying all possible lengths of the beginning part of the typed string as the original string.
Each time, compare the current assumed 'original' string to see if you can form the typed string by adding extra characters into the 'original' string.
If we find a match, that means we've found a possible original string.
If we go through all possibilities without a match, it means there's no original string that could have created the typed string.

Code Implementation

def find_original_string_brute_force(typed_string):
    for original_length in range(1, len(typed_string) + 1):
        possible_original = typed_string[:original_length]

        # Check if this possible original string can produce the typed string
        if can_form_typed_string(possible_original, typed_string):
            return possible_original

    return ""

def can_form_typed_string(possible_original, typed_string):
    original_index = 0
    typed_index = 0

    while original_index < len(possible_original) and typed_index < len(typed_string):
        if possible_original[original_index] == typed_string[typed_index]:
            original_index += 1
            typed_index += 1
        elif typed_index > 0 and typed_string[typed_index] == typed_string[typed_index - 1]:
            # Allow for repeated characters in typed string.
            typed_index += 1
        else:
            return False

    # The original string should be fully traversed to form the typed string.
    if original_index != len(possible_original):
        return False

    #Remaining typed characters must match the last original character.
    while typed_index < len(typed_string):
        if typed_string[typed_index] != possible_original[original_index - 1]:
            return False
        typed_index += 1

    return True

Big(O) Analysis

Time Complexity

O(n^2) – The algorithm iterates through all possible prefixes of the typed string, where n is the length of the typed string. For each prefix considered as a potential original string, it compares this prefix against the remaining part of the typed string to see if typos could have generated the typed string. This comparison in the worst case involves comparing each character of the prefix with the remaining part of the typed string. Thus, we potentially have a nested loop, where the outer loop iterates up to n and the inner loop also iterates up to n. This results in approximately n * n comparisons in the worst-case scenario. Therefore, the time complexity is O(n^2).

Space Complexity

O(N) – The plain English explanation describes trying out all possible prefixes of the typed string as potential original strings. In the worst-case scenario, each prefix might be stored or processed in some way to check if it can form the typed string by adding extra characters. This implies the existence of temporary string variables or data structures to hold these prefixes. If N is the length of the typed string, the algorithm could potentially store prefixes of lengths 1, 2, ..., N. The memory used to store or process these prefixes could grow linearly with the input size, making the auxiliary space complexity O(N).

Optimal Solution

Approach

We're given a longer string and a shorter string, where the longer string contains the original message with some extra characters added in. The goal is to figure out what the original message was by carefully comparing the two strings, character by character.

Here's how the algorithm would work step-by-step:

Start by comparing the first characters of both strings.
If the characters match, move to the next character in both strings. This means the character was part of the original message.
If the characters don't match, move to the next character in the longer string only. This means the character was an extra one that needs to be skipped.
Keep repeating these steps until you reach the end of the longer string.
The characters you kept from the longer string while moving forward in both strings form the original message.

Code Implementation

def find_original_string(long_string, short_string):
    long_string_index = 0
    short_string_index = 0
    original_message = ''

    while long_string_index < len(long_string):
        # Characters match, add to result and advance both pointers.
        if short_string_index < len(short_string) and \
           long_string[long_string_index] == short_string[short_string_index]:
            original_message += long_string[long_string_index]

            long_string_index += 1
            short_string_index += 1
        else:
            # Characters don't match, advance only the long string pointer.
            # This skips the extra characters.
            long_string_index += 1

    return original_message

Big(O) Analysis

Time Complexity

O(n) – We iterate through both strings, 'longer' and 'shorter', using a single while loop. In each iteration, we either increment both string pointers if the characters match, or only increment the 'longer' string pointer if they don't. The loop continues until we reach the end of the 'longer' string. Therefore, the time complexity is directly proportional to the length of the 'longer' string, which we can denote as 'n'. Thus, the time complexity is O(n).

Space Complexity

O(1) – The provided algorithm compares characters directly without using any auxiliary data structures to store intermediate results. It only needs to maintain two index variables to traverse the longer and shorter strings. These index variables occupy a constant amount of space, irrespective of the lengths of the input strings. Therefore, the space complexity is constant.

Edge Cases

Case	How to Handle
s is null or empty	Return an empty string if s is null or empty as there's no typed string.
t is null or empty	Return s if t is null or empty, since an empty displayed string means all characters in s were potentially accidental.
Length of s is less than length of t	Return an empty string since t can't be a subsequence of s if it's longer.
s and t are identical	Return s (or t) since the original string is the same as the final displayed string.
t is not a subsequence of s	Return an empty string because no valid original string can be derived.
s contains duplicate characters and t utilizes specific occurrences	The subsequence matching should respect the order of characters in both s and t.
Maximum length strings for s and t exceeding memory limits	The solution should use an iterative approach rather than recursion to avoid stack overflow, and should consider memory usage when constructing the result string.
s contains only one character and t is empty	Return s since the character in s was removed to create the empty t.

s is null or empty

How to Handle:

Return an empty string if s is null or empty as there's no typed string.

t is null or empty

How to Handle:

Return s if t is null or empty, since an empty displayed string means all characters in s were potentially accidental.

Length of s is less than length of t

How to Handle:

Return an empty string since t can't be a subsequence of s if it's longer.

s and t are identical

How to Handle:

Return s (or t) since the original string is the same as the final displayed string.

t is not a subsequence of s

How to Handle:

Return an empty string because no valid original string can be derived.

s contains duplicate characters and t utilizes specific occurrences

How to Handle:

The subsequence matching should respect the order of characters in both s and t.

Maximum length strings for s and t exceeding memory limits

How to Handle:

The solution should use an iterative approach rather than recursion to avoid stack overflow, and should consider memory usage when constructing the result string.

s contains only one character and t is empty

How to Handle:

Return s since the character in s was removed to create the empty t.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What should I return if it is not possible to form string `t` from string `s` by removing characters?
Are `s` and `t` guaranteed to be non-null or non-empty strings?
If there are multiple valid original typed strings that could form `t`, is any one acceptable, or is there a specific original typed string I should return (e.g., the lexicographically smallest)?
Are there any constraints on the characters that `s` and `t` can contain (e.g., only lowercase letters, ASCII characters)?
What are the maximum lengths of the strings `s` and `t`?

Brute Force Solution

Approach

The basic idea is to try out all possible ways to build the original string. We'll check each possibility to see if it matches the longer, typed-out string.

Here's how the algorithm would work step-by-step:

Start by assuming the first character of the typed string is from the original string.
Then, check if the rest of the typed string could have been created by accidentally adding extra characters after that first character.
Next, assume the first two characters of the typed string are from the original string.
Again, see if the remaining characters of the typed string could be the result of typos after those two characters.
Keep doing this, trying all possible lengths of the beginning part of the typed string as the original string.
Each time, compare the current assumed 'original' string to see if you can form the typed string by adding extra characters into the 'original' string.
If we find a match, that means we've found a possible original string.
If we go through all possibilities without a match, it means there's no original string that could have created the typed string.

Code Implementation

def find_original_string_brute_force(typed_string):
    for original_length in range(1, len(typed_string) + 1):
        possible_original = typed_string[:original_length]

        # Check if this possible original string can produce the typed string
        if can_form_typed_string(possible_original, typed_string):
            return possible_original

    return ""

def can_form_typed_string(possible_original, typed_string):
    original_index = 0
    typed_index = 0

    while original_index < len(possible_original) and typed_index < len(typed_string):
        if possible_original[original_index] == typed_string[typed_index]:
            original_index += 1
            typed_index += 1
        elif typed_index > 0 and typed_string[typed_index] == typed_string[typed_index - 1]:
            # Allow for repeated characters in typed string.
            typed_index += 1
        else:
            return False

    # The original string should be fully traversed to form the typed string.
    if original_index != len(possible_original):
        return False

    #Remaining typed characters must match the last original character.
    while typed_index < len(typed_string):
        if typed_string[typed_index] != possible_original[original_index - 1]:
            return False
        typed_index += 1

    return True

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Start by comparing the first characters of both strings.
If the characters match, move to the next character in both strings. This means the character was part of the original message.
If the characters don't match, move to the next character in the longer string only. This means the character was an extra one that needs to be skipped.
Keep repeating these steps until you reach the end of the longer string.
The characters you kept from the longer string while moving forward in both strings form the original message.

Code Implementation

def find_original_string(long_string, short_string):
    long_string_index = 0
    short_string_index = 0
    original_message = ''

    while long_string_index < len(long_string):
        # Characters match, add to result and advance both pointers.
        if short_string_index < len(short_string) and \
           long_string[long_string_index] == short_string[short_string_index]:
            original_message += long_string[long_string_index]

            long_string_index += 1
            short_string_index += 1
        else:
            # Characters don't match, advance only the long string pointer.
            # This skips the extra characters.
            long_string_index += 1

    return original_message

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
s is null or empty	Return an empty string if s is null or empty as there's no typed string.
t is null or empty	Return s if t is null or empty, since an empty displayed string means all characters in s were potentially accidental.
Length of s is less than length of t	Return an empty string since t can't be a subsequence of s if it's longer.
s and t are identical	Return s (or t) since the original string is the same as the final displayed string.
t is not a subsequence of s	Return an empty string because no valid original string can be derived.
s contains duplicate characters and t utilizes specific occurrences	The subsequence matching should respect the order of characters in both s and t.
Maximum length strings for s and t exceeding memory limits	The solution should use an iterative approach rather than recursion to avoid stack overflow, and should consider memory usage when constructing the result string.
s contains only one character and t is empty	Return s since the character in s was removed to create the empty t.

s is null or empty

How to Handle:

Return an empty string if s is null or empty as there's no typed string.

t is null or empty

How to Handle:

Return s if t is null or empty, since an empty displayed string means all characters in s were potentially accidental.

Length of s is less than length of t

How to Handle:

Return an empty string since t can't be a subsequence of s if it's longer.

s and t are identical

How to Handle:

Return s (or t) since the original string is the same as the final displayed string.

t is not a subsequence of s

How to Handle:

Return an empty string because no valid original string can be derived.

s contains duplicate characters and t utilizes specific occurrences

How to Handle:

The subsequence matching should respect the order of characters in both s and t.

Maximum length strings for s and t exceeding memory limits

How to Handle:

The solution should use an iterative approach rather than recursion to avoid stack overflow, and should consider memory usage when constructing the result string.

s contains only one character and t is empty

How to Handle:

Return s since the character in s was removed to create the empty t.