We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Check if an Original String Exists Given Two Encoded Strings

Number: 2184

Difficulty: Hard

Paid? No

Companies: Meta, BitGo

Problem Description

Given two encoded strings s1 and s2 where each string is formed by taking an original string of lowercase letters, splitting it into a sequence of non-empty substrings, and then optionally replacing some of these substrings by their length (as a numeric string), determine whether there exists at least one original string that could have generated both s1 and s2. The encoded strings consist only of lowercase English letters and digits 1–9. The challenge is to “match” the two encoded strings by accounting for the flexibility of numeric replacements.

Key Insights

  • The encoded strings mix letters and numeric strings (which represent arbitrary-length substrings) making direct matching non-trivial.
  • We can use a recursive (backtracking) approach with memoization (dynamic programming) to simulate the decoding process.
  • Maintain two indices (one for each encoded string) and a running “difference” (diff) that tracks the imbalance in the number of literal characters processed (i.e. how many extra letters one decode path has over the other).
  • When encountering digits, explore all valid number interpretations (remembering that consecutive digits can form numbers up to 3 digits long).
  • Letters must match exactly, but if one side has a pending “skip” (due to a previously encountered number) then the recursion adjusts the diff accordingly.
  • The main trick lies in interpreting digits as flexible “gaps” in the original string reconstruction and using DFS to try all valid splits.

Space and Time Complexity

Time Complexity: O(n1 * n2 * maxDiff) in the worst-case scenario, where n1 and n2 are the lengths of s1 and s2 and maxDiff is bounded by the maximum possible digit sum interpreted. Space Complexity: O(n1 * n2 * maxDiff) for the memoization state.

Solution

We use a DFS recursive approach with memoization. The function recursively processes characters in s1 and s2 with pointers i and j, and a “diff” that indicates how many extra decoded characters (letters) one string currently has compared to the other. When a digit is encountered on one side, we try all valid number interpretations (since digits might represent different substring lengths). If a letter is encountered, it must match the corresponding decoded letter from the other string; otherwise, we adjust the diff accordingly. The recursion ends successfully when both indices reach the end of their respective strings and the diff is 0. This solution uses recursion combined with memoization to avoid redundant computations.

Code Solutions

def possiblyEquals(s1: str, s2: str) -> bool:
    from functools import lru_cache
    
    # Use DFS with memoization. i: index in s1, j: index in s2, diff: (s1 decoded letters) - (s2 decoded letters)
    @lru_cache(maxsize=None)
    def dfs(i, j, diff):
        # When both strings are finished, we need the diff to be 0 (balanced decoded letters)
        if i == len(s1) and j == len(s2):
            return diff == 0
        
        # Process s1: if there is an unbalanced diff and we can add letters from s1
        if i < len(s1) and s1[i].isdigit():
            num = 0
            # try to form a number from consecutive digits
            for k in range(i, min(i + 3, len(s1))):
                if not s1[k].isdigit():
                    break
                num = num * 10 + int(s1[k])
                # consuming a number from s1 increases diff
                if dfs(k + 1, j, diff + num):
                    return True
        
        # Process s2: similarly, try digits from s2
        if j < len(s2) and s2[j].isdigit():
            num = 0
            for k in range(j, min(j + 3, len(s2))):
                if not s2[k].isdigit():
                    break
                num = num * 10 + int(s2[k])
                # consuming a number from s2 decreases diff
                if dfs(i, k + 1, diff - num):
                    return True
        
        # Match literal letters when possible.
        # If diff > 0, that means s1 has extra letters waiting to be matched against s2.
        if diff > 0:
            if j < len(s2) and s2[j].isalpha():
                # Consume one letter from s2 to reduce diff.
                if dfs(i, j + 1, diff - 1):
                    return True
        # If diff < 0, that means s2 has extra letters waiting to be matched against s1.
        elif diff < 0:
            if i < len(s1) and s1[i].isalpha():
                if dfs(i + 1, j, diff + 1):
                    return True
        # If diff == 0, both must have letters to match.
        else:
            if i < len(s1) and j < len(s2) and s1[i].isalpha() and s2[j].isalpha() and s1[i] == s2[j]:
                if dfs(i + 1, j + 1, diff):
                    return True
        return False

    return dfs(0, 0, 0)


# Example usage:
print(possiblyEquals("a5b", "c5b"))   # Output: False; explained in Example 3.
print(possiblyEquals("l123e", "44"))   # Output: True
← Back to All Questions