Scramble String - Practice Coding Problems

Scramble String - Problem

We can scramble a string s to get a string t using the following algorithm:

If the length of the string is 1, stop.
If the length of the string is > 1, do the following:
- Split the string into two non-empty substrings at a random index, i.e., if the string is s, divide it to x and y where s = x + y.
- Randomly decide to swap the two substrings or to keep them in the same order. i.e., after this step, s may become s = x + y or s = y + x.
- Apply step 1 recursively on each of the two substrings x and y.

Given two strings s1 and s2 of the same length, return true if s2 is a scrambled string of s1, otherwise, return false.

Input & Output

Example 1 — Basic Scramble

$ Input: s1 = "great", s2 = "rgeat"

› Output: true

💡 Note: "great" can be scrambled to "rgeat" by splitting at position 2: "gr|eat" → swap to "eat|gr" → further scramble "eat" to "rge" → result "rgeat"

Example 2 — Not a Scramble

$ Input: s1 = "abcde", s2 = "caebd"

› Output: false

💡 Note: No valid scrambling sequence can transform "abcde" into "caebd" following the scramble rules

Example 3 — Identical Strings

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

› Output: true

💡 Note: Single character strings that are identical are always scrambles of each other

Constraints

1 ≤ s1.length, s2.length ≤ 30
s1 and s2 consist of lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input

Two strings s1 and s2 of same length

Process

Check if s2 can be obtained by scrambling s1

Output

Return true if scramble is possible, false otherwise

Key Takeaway

🎯 Key Insight: A string is a scramble if it can be split where parts match in original or swapped order recursively

Asked in

G Google 35 F Facebook 28 a Amazon 22 M Microsoft 18

The key insight is that two strings are scrambles if they can be split where the parts match in either original or swapped order recursively. Best approach is memoized recursion or 3D dynamic programming. Time: O(n³), Space: O(n³)

Common Approaches

Approach	Time	Space	Notes
✓ 3D Dynamic Programming	O(n⁴)	O(n³)	Bottom-up DP table storing results for all substring combinations and lengths
Recursive Brute Force	O(4^n)	O(n)	Try all possible split points and check both swap and non-swap cases recursively
Recursion with Memoization	O(n³)	O(n³)	Same recursive approach but cache results to avoid redundant calculations

3D Dynamic Programming — Algorithm Steps

Step 1: Create 3D DP table dp[i][j][len]
Step 2: Initialize base case for length 1
Step 3: Fill table for increasing lengths using previous results

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize Length 1

Set dp[i][j][1] = true if s1[i] == s2[j]

Build Larger Lengths

Use smaller length results to build longer substring matches

Final Answer

dp[0][0][n] contains whether entire strings are scrambles

Code -

solution.c — C

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

bool solution(char* s1, char* s2) {
    int len1 = strlen(s1);
    int len2 = strlen(s2);
    
    if (len1 != len2) return false;
    if (strcmp(s1, s2) == 0) return true;
    
    int n = len1;
    // dp[i][j][length] = true if s1[i:i+length] is scramble of s2[j:j+length]
    bool dp[n][n][n + 1];
    memset(dp, false, sizeof(dp));
    
    // Base case: length 1
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            dp[i][j][1] = (s1[i] == s2[j]);
        }
    }
    
    // Fill for lengths 2 to n
    for (int length = 2; length <= n; length++) {
        for (int i = 0; i <= n - length; i++) {
            for (int j = 0; j <= n - length; j++) {
                // Try all possible split positions
                for (int k = 1; k < length; k++) {
                    // Non-swapped case
                    if (dp[i][j][k] && dp[i + k][j + k][length - k]) {
                        dp[i][j][length] = true;
                        break;
                    }
                    
                    // Swapped case
                    if (dp[i][j + length - k][k] && dp[i + k][j][length - k]) {
                        dp[i][j][length] = true;
                        break;
                    }
                }
            }
        }
    }
    
    return dp[0][0][n];
}

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

Time & Space Complexity

Time Complexity

⏱️

O(n⁴)

Three nested loops for i,j,len plus inner loop for split position k

✓ Linear Growth

Space Complexity

O(n³)

3D DP table of size n×n×n to store all subproblem results

⚠ Quadratic Space

28.5K Views

Medium Frequency

~25 min Avg. Time

892 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

3D Dynamic Programming — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler