Skip to main content
Talentd

Check if an Original String Exists Given Two Encoded Strings - Solution & Explanation

HardStringDynamic Programming10 min readAsked at: Meta, BitGo
Practice this problem

Problem Statement

An original string, consisting of lowercase English letters, can be encoded by the following steps:

  • Arbitrarily split it into a sequence of some number of non-empty substrings.
  • Arbitrarily choose some elements (possibly none) of the sequence, and replace each with its length (as a numeric string).
  • Concatenate the sequence as the encoded string.

For example, one way to encode an original string "abcdefghijklmnop" might be:

  • Split it as a sequence: ["ab", "cdefghijklmn", "o", "p"].
  • Choose the second and third elements to be replaced by their lengths, respectively. The sequence becomes ["ab", "12", "1", "p"].
  • Concatenate the elements of the sequence to get the encoded string: "ab121p".

Given two encoded strings s1 and s2, consisting of lowercase English letters and digits 1-9 (inclusive), return true if there exists an original string that could be encoded as both s1 and s2. Otherwise, return false.

Note: The test cases are generated such that the number of consecutive digits in s1 and s2 does not exceed 3.

 

Example 1:

Input: s1 = "internationalization", s2 = "i18n"
Output: true
Explanation: It is possible that "internationalization" was the original string.
- "internationalization" 
  -> Split:       ["internationalization"]
  -> Do not replace any element
  -> Concatenate:  "internationalization", which is s1.
- "internationalization"
  -> Split:       ["i", "nternationalizatio", "n"]
  -> Replace:     ["i", "18",                 "n"]
  -> Concatenate:  "i18n", which is s2

Example 2:

Input: s1 = "l123e", s2 = "44"
Output: true
Explanation: It is possible that "leetcode" was the original string.
- "leetcode" 
  -> Split:      ["l", "e", "et", "cod", "e"]
  -> Replace:    ["l", "1", "2",  "3",   "e"]
  -> Concatenate: "l123e", which is s1.
- "leetcode" 
  -> Split:      ["leet", "code"]
  -> Replace:    ["4",    "4"]
  -> Concatenate: "44", which is s2.

Example 3:

Input: s1 = "a5b", s2 = "c5b"
Output: false
Explanation: It is impossible.
- The original string encoded as s1 must start with the letter 'a'.
- The original string encoded as s2 must start with the letter 'c'.

 

Constraints:

  • 1 <= s1.length, s2.length <= 40
  • s1 and s2 consist of digits 1-9 (inclusive), and lowercase English letters only.
  • The number of consecutive digits in s1 and s2 does not exceed 3.

Approach Overview

Problem Overview: Two strings contain lowercase letters and digits. Digits represent the length of skipped characters in the original string. The task is to determine whether both encoded strings could decode to the same original string.

Approach 1: Backtracking with Two-Pointers (State Difference Tracking) (Time: O(n * m * D), Space: O(n * m * D))

Traverse both encoded strings using two pointers. Maintain a diff value representing the difference between how many characters each string still needs to match from numeric expansions. When encountering digits, parse all possible numeric combinations (e.g., "12" could mean 1+2 or 12) and update diff. If diff > 0, the first string has unmatched characters; if diff < 0, the second string does. When both pointers point to letters and diff == 0, the letters must match. Use recursion with memoization on (i, j, diff) to avoid recomputation. This approach naturally models the decoding process and works well with pruning.

Approach 2: Dynamic Programming with State Compression (Time: O(n * m * D), Space: O(n * m * D))

Use dynamic programming where the state dp[i][j] stores a set of possible diff values after processing prefixes of both strings. The diff represents the same pending length difference as in the backtracking approach. When digits appear, expand them into all valid numeric values and update the difference. When letters appear, match them directly if diff == 0, or consume pending difference if one side still represents skipped characters. State compression limits the difference range (typically around -1000 to 1000), keeping the DP manageable. This iterative version avoids recursion and systematically explores all valid states.

Both approaches rely heavily on parsing digit sequences and tracking how many characters each encoded string represents without explicitly reconstructing the original string.

Recommended for interviews: Backtracking with memoization is the most commonly discussed solution. It clearly models the decoding process and demonstrates strong understanding of string parsing and backtracking. The DP state compression variant shows deeper mastery of dynamic programming and is useful when interviewers want an iterative formulation.

Approach 1: Backtracking with Two-Pointers

This approach uses two pointers to iterate through the encoded strings s1 and s2. For each character, we check whether it is a letter or a digit. If it's a letter, both strings must match directly at that position. If it's a digit, we use it to determine how many characters we can skip in the original string the encoded version represents. If the two strings can be navigated successfully considering these rules, then the original string can be encoded to both, otherwise, it cannot be.

The Python code employs a recursive backtracking function backtrack with indices i and j iterating through s1 and s2 respectively. It also maintains p1 and p2 to track the actual length traversed in the potential common original string. When digits are encountered, they are converted into a number and used to jump ahead in the original string's length being tracked. This process continues recursively and returns true if a valid path is found.

Code

PythonJavaScript

Python

JavaScript

Complexity

Time Complexity: O(n * m) where n and m are the lengths of s1 and s2 respectively in the worst case. Space Complexity: O(n + m) for recursion stack space.

Try this approach in the editor →

Approach 2: Dynamic Programming with State Compression

Dynamic Programming (DP) is leveraged here to store intermediate results and avoid redundant calculations when matching parts of the strings s1 and s2. The DP table will keep track of whether a specific substring length of 's1' can match a specific substring length of 's2'. The difference lies in using DP instead of backtracking. This method is more memory intensive but can potentially reduce redundant recursive calls.

The C++ code uses a DP table with dimensions (s1.length + 1) x (s2.length + 1), where each state dp[i][j] represents if the first i characters of s1 can match with the first j characters of s2. We iterate through both strings, updating the DP table by interpreting substrings of digits into numbers and ensuring correct passages through the encoded characters.

Code

C++Java

C++

Java

Complexity

Time Complexity: O(n * m). Space Complexity: O(n * m) where n and m are lengths of s1 and s2.

Try this approach in the editor →

Approach 3: Default Approach

Code

TypeScript

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Backtracking with Two-Pointers

Time Complexity: O(n * m) where n and m are the lengths of s1 and s2 respectively in the worst case. Space Complexity: O(n + m) for recursion stack space.

Dynamic Programming with State Compression

Time Complexity: O(n * m). Space Complexity: O(n * m) where n and m are lengths of s1 and s2.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Backtracking with Two-PointersO(n * m * D)O(n * m * D)Interview-friendly solution that models decoding logic clearly
Backtracking + MemoizationO(n * m * D)O(n * m * D)Prevents repeated state exploration in recursive solutions
Dynamic Programming with State CompressionO(n * m * D)O(n * m * D)Best when you want an iterative DP formulation without recursion

Video Solution

【每日一题】LeetCode 2060. Check if an Original String Exists Given Two Encoded Strings • Huifeng Guan • 2,665 views views

Watch 3 more video solutions →

Frequently Asked Questions

Is Check if an Original String Exists Given Two Encoded Strings easy or hard?
The problem is classified as Hard on LeetCode. Handling multiple digit interpretations, managing the difference between expansions, and preventing exponential recursion require strong understanding of dynamic programming and state memoization.
Check if an Original String Exists Given Two Encoded Strings Python/Java solution
Python implementations usually use recursive backtracking with memoization using a dictionary or functools.lru_cache. Java solutions often use DFS with a HashSet for visited states or a DP table storing possible difference values.
How to solve Check if an Original String Exists Given Two Encoded Strings in O(n)?
A strict O(n) solution is not practical because both encoded strings must be explored together. The optimal solutions use either memoized backtracking or dynamic programming with complexity around O(n * m * D), which efficiently handles all valid digit expansions and letter matches.
What is the best approach for Check if an Original String Exists Given Two Encoded Strings?
Backtracking with two pointers and memoization is the most common solution. Track a difference value representing how many characters one encoded string still needs to match relative to the other. Memoizing states (i, j, diff) avoids repeated exploration and keeps the complexity around O(n * m * D).
Is Check if an Original String Exists Given Two Encoded Strings asked at Google/Amazon/Meta?
Hard string and dynamic programming problems like this commonly appear in interviews at companies such as Google, Meta, and Amazon. The problem tests recursive state exploration, memoization, and handling of complex string encoding rules.
What data structure is used in Check if an Original String Exists Given Two Encoded Strings?
Key structures include recursion stacks, hash sets or maps for memoization, and dynamic programming tables. The state typically tracks indices of both strings along with a difference value representing pending unmatched characters.
What is the time complexity of Check if an Original String Exists Given Two Encoded Strings?
The typical complexity is O(n * m * D), where n and m are the lengths of the encoded strings and D is the range of possible difference values (roughly ±1000). Each state represents positions in both strings plus the pending character difference created by numeric expansions.

Ready to solve this problem?

Practice Check if an Original String Exists Given Two Encoded Strings with our built-in code editor and test cases.

Practice on FleetCode
Previous

Check If Two String Arrays are Equivalent

Next

Valid Word Abbreviation