Find the Original Typed String I

Difficulty: Easy | Acceptance: 72.00% | Paid: No Topics: String

Alice is trying to type a string target. She might have typed some characters multiple times. Given typed and target, return the maximum number of times she could have pressed a key to get typed from target. If it is impossible to get typed from target, return 0.

• Examples
• Constraints
• Two Pointers
• Run-Length Encoding
• Recursive Depth First Search

Examples

Example 1:

Input: target = "abcd", typed = "aaabbbcccddd"
Output: 12
Explanation: 'a' pressed 3 times, 'b' pressed 3 times, 'c' pressed 3 times, 'd' pressed 3 times. Total 12.

Example 2:

Input: target = "abcd", typed = "aaabbbcccdd"
Output: 0
Explanation: 'd' is not pressed enough times to match the target's requirement or structure implies mismatch.

Example 3:

Input: target = "a", typed = "aaaaaaaaaaaaa"
Output: 13
Explanation: 'a' pressed 13 times.

Constraints

1 <= target.length, typed.length <= 1000
target and typed consist of lowercase English letters.

Two Pointers

Intuition We can iterate through both strings simultaneously using two pointers. If characters match, we advance both. If they don’t match, we check if the current character in typed is a repeat of the previous valid character. If it is, we only advance the typed pointer. Otherwise, the strings are incompatible.

Steps

• Initialize pointers i for target and j for typed.
• Loop while j is within bounds of typed.
• If target[i] matches typed[j], increment both i and j.
• Else if typed[j] matches typed[j-1] (and j > 0), increment j (it’s a long press).
• Else, return 0 (invalid character).
• After the loop, if i has reached the end of target, return len(typed). Otherwise, return 0.

class Solution:
    def possibleStringCount(self, target: str, typed: str) -> int:
        i = 0
        for j in range(len(typed)):
            if i < len(target) and target[i] == typed[j]:
                i += 1
            elif j == 0 or typed[j] != typed[j-1]:
                return 0
        return len(typed) if i == len(target) else 0

Complexity

• Time: O(n + m), where n and m are the lengths of target and typed.
• Space: O(1)
• Notes: Most efficient approach with constant space.

Run-Length Encoding

Intuition We can compress both strings into groups of consecutive characters (Run-Length Encoding). Then, we compare the groups. For the strings to be compatible, they must have the same sequence of characters, and the count in typed must be greater than or equal to the count in target for each character.

Steps

• Create a helper function to generate a list of [char, count] pairs for a string.
• Generate groups for target and typed.
• If the number of groups differs, return 0.
• Iterate through corresponding groups. If characters differ or typed count is less than target count, return 0.
• If all checks pass, return len(typed).

class Solution:
    def possibleStringCount(self, target: str, typed: str) -> int:
        def get_groups(s):
            if not s: return []
            groups = []
            curr = s[0]
            cnt = 1
            for c in s[1:]:
                if c == curr:
                    cnt += 1
                else:
                    groups.append((curr, cnt))
                    curr = c
                    cnt = 1
            groups.append((curr, cnt))
            return groups

        g1 = get_groups(target)
        g2 = get_groups(typed)

        if len(g1) != len(g2):
            return 0

        for (c1, n1), (c2, n2) in zip(g1, g2):
            if c1 != c2 or n2 < n1:
                return 0
        return len(typed)

Complexity

• Time: O(n + m)
• Space: O(n + m) to store the groups.
• Notes: More memory intensive but conceptually simple by breaking down the structure.

Recursive Depth First Search

Intuition We can define a recursive function that checks if the remaining suffixes of target and typed are compatible. At each step, we try to match the current characters or consume a repeated character in typed.

Steps

• Define a recursive function dfs(i, j) where i is index in target and j is index in typed.
• Base case: if i reaches end of target and j reaches end of typed, return true.
• If j reaches end of typed but i does not, return false.
• If target[i] == typed[j], recurse with dfs(i + 1, j + 1).
• If typed[j] == typed[j-1] (long press), recurse with dfs(i, j + 1).
• If neither works, return false.
• If the top-level call returns true, return len(typed), else 0.

class Solution:
    def possibleStringCount(self, target: str, typed: str) -> int:
        memo = {}
        def dfs(i, j):
            if i == len(target) and j == len(typed):
                return True
            if j == len(typed):
                return False
            
            if (i, j) in memo:
                return memo[(i, j)]
            
            res = False
            if i < len(target) and target[i] == typed[j]:
                res = dfs(i + 1, j + 1)
            if not res and j > 0 and typed[j] == typed[j-1]:
                res = dfs(i, j + 1)
            
            memo[(i, j)] = res
            return res

        return len(typed) if dfs(0, 0) else 0

Complexity

• Time: O(n * m) in the worst case without memoization, O(n + m) with memoization.
• Space: O(n * m) for the recursion stack and memoization table.
• Notes: Less efficient than the iterative two-pointer approach due to overhead.