Check if an Original String Exists Given Two Encoded Strings

Check if an Original String Exists Given Two Encoded Strings - Problem

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.

Input & Output

Example 1 — Different Interpretations

$ Input: s1 = "a5b", s2 = "a5b"

› Output: true

💡 Note: Both strings are identical, so they can definitely encode the same original string (either "a5b" or "a" + 5 characters + "b")

Example 2 — Number as Length

$ Input: s1 = "ab", s2 = "a2"

› Output: false

💡 Note: s1 = "ab" means original has 'a' then 'b'. s2 = "a2" could mean 'a' + 2 characters, but that would be 3 total chars vs 2 in s1

Example 3 — Complex Case

$ Input: s1 = "a5b", s2 = "abc"

› Output: false

💡 Note: s1 could be "a5b" (3 chars) or "a" + 5chars + "b" (7 chars). s2 is "abc" (3 chars). Only 3-char interpretation works, but "a5b" ≠ "abc"

Constraints

1 ≤ s1.length, s2.length ≤ 40
s1 and s2 consist of digits 1-9 and lowercase English letters
The number of consecutive digits in s1 and s2 does not exceed 3

Visualization

Tap to expand

Understanding the Visualization

Input

Two encoded strings with letters and digits

Process

Try different interpretations of digits

Output

True if both can encode same original

Key Takeaway

🎯 Key Insight: Track character count difference to determine if both strings can represent the same original

Asked in

G Google 42 f Facebook 38 M Microsoft 25

The key insight is to track the character difference between the two strings as we decode them. We use recursive exploration with memoization to try all possible interpretations of digits (as lengths or literals). Best approach is memoized recursion. Time: O(n×m×D), Space: O(n×m×D).

Common Approaches

Approach	Time	Space	Notes
✓ Memoized Recursion	O(n × m × D)	O(n × m × D)	Cache results to avoid recomputing same states
Recursive Backtracking	O(2^(n+m))	O(n+m)	Try all possible interpretations of numbers recursively

Memoized Recursion — Algorithm Steps

Use recursion with memoization
Cache results by (position1, position2, difference)
Return cached result if state already computed
Otherwise compute and cache before returning

Visualization

Tap to expand

Step-by-Step Walkthrough

State Key

Create unique key (i, j, diff)

Cache Lookup

Check if result already computed

Store Result

Cache new results for future use

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <stdbool.h>

#define MAX_STATES 100000

typedef struct {
    int i, j, diff;
    bool result;
} MemoEntry;

MemoEntry memo[MAX_STATES];
int memoSize = 0;

bool getMemo(int i, int j, int diff) {
    for (int k = 0; k < memoSize; k++) {
        if (memo[k].i == i && memo[k].j == j && memo[k].diff == diff) {
            return memo[k].result;
        }
    }
    return false;
}

void setMemo(int i, int j, int diff, bool result) {
    if (memoSize < MAX_STATES) {
        memo[memoSize].i = i;
        memo[memoSize].j = j;
        memo[memoSize].diff = diff;
        memo[memoSize].result = result;
        memoSize++;
    }
}

bool hasMemo(int i, int j, int diff) {
    for (int k = 0; k < memoSize; k++) {
        if (memo[k].i == i && memo[k].j == j && memo[k].diff == diff) {
            return true;
        }
    }
    return false;
}

bool solve(const char* s1, const char* s2, int i, int j, int diff, int len1, int len2) {
    if (hasMemo(i, j, diff)) {
        return getMemo(i, j, diff);
    }
    
    if (i == len1 && j == len2) {
        bool result = diff == 0;
        setMemo(i, j, diff, result);
        return result;
    }
    
    bool result = false;
    
    if (i < len1 && isalpha(s1[i])) {
        result = solve(s1, s2, i + 1, j, diff + 1, len1, len2);
    } else if (j < len2 && isalpha(s2[j])) {
        result = solve(s1, s2, i, j + 1, diff - 1, len1, len2);
    } else if (i < len1 && isdigit(s1[i])) {
        int num = 0;
        int maxK = (i + 3 < len1) ? i + 3 : len1;
        for (int k = i; k < maxK; k++) {
            if (isdigit(s1[k])) {
                num = num * 10 + (s1[k] - '0');
                if (solve(s1, s2, k + 1, j, diff + num, len1, len2)) {
                    result = true;
                    break;
                }
            } else {
                break;
            }
        }
    } else if (j < len2 && isdigit(s2[j])) {
        int num = 0;
        int maxK = (j + 3 < len2) ? j + 3 : len2;
        for (int k = j; k < maxK; k++) {
            if (isdigit(s2[k])) {
                num = num * 10 + (s2[k] - '0');
                if (solve(s1, s2, i, k + 1, diff - num, len1, len2)) {
                    result = true;
                    break;
                }
            } else {
                break;
            }
        }
    }
    
    setMemo(i, j, diff, result);
    return result;
}

bool solution(const char* s1, const char* s2) {
    memoSize = 0;
    return solve(s1, s2, 0, 0, 0, strlen(s1), strlen(s2));
}

int main() {
    char s1[1001], s2[1001];
    fgets(s1, sizeof(s1), stdin);
    fgets(s2, sizeof(s2), stdin);
    s1[strcspn(s1, "\n")] = 0;
    s2[strcspn(s2, "\n")] = 0;
    bool result = solution(s1, s2);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × m × D)

n and m are string lengths, D is maximum possible difference value

✓ Linear Growth

Space Complexity

O(n × m × D)

Memoization cache stores results for all unique states

⚡ Linearithmic Space

23.5K Views

Medium Frequency

~35 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Memoized Recursion — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler