Scale Engineer

Scramble String

Hard
#0087Time: O(n * C_n) ~ O(4^n / n^(3/2))Space: O(n)5 companies
Patterns
Dynamic Programming
Data structures
String
Companies
AmazonGoogleMedia.netRubrik

Prompt

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

  1. If the length of the string is 1, stop.
  2. 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.

 

Example 1:

Input: s1 = "great", s2 = "rgeat"
Output: true
Explanation: One possible scenario applied on s1 is:
"great" --> "gr/eat" // divide at random index.
"gr/eat" --> "gr/eat" // random decision is not to swap the two substrings and keep them in order.
"gr/eat" --> "g/r / e/at" // apply the same algorithm recursively on both substrings. divide at random index each of them.
"g/r / e/at" --> "r/g / e/at" // random decision was to swap the first substring and to keep the second substring in the same order.
"r/g / e/at" --> "r/g / e/ a/t" // again apply the algorithm recursively, divide "at" to "a/t".
"r/g / e/ a/t" --> "r/g / e/ a/t" // random decision is to keep both substrings in the same order.
The algorithm stops now, and the result string is "rgeat" which is s2.
As one possible scenario led s1 to be scrambled to s2, we return true.

Example 2:

Input: s1 = "abcde", s2 = "caebd"
Output: false

Example 3:

Input: s1 = "a", s2 = "a"
Output: true

 

Constraints:

  • s1.length == s2.length
  • 1 <= s1.length <= 30
  • s1 and s2 consist of lowercase English letters.

Approaches

3 approaches with complexity analysis and trade-offs.

This approach directly translates the problem's recursive definition into a function. It explores every possible way s1 can be partitioned and potentially swapped, checking if any of these recursive constructions result in s2. While conceptually simple, it's computationally very expensive.

Algorithm

  • Define a recursive function isScramble(s1, s2).
  • Base Case: If s1 and s2 are identical, return true.
  • Pruning: Check if s1 and s2 are anagrams. This can be done by sorting or using a frequency map. If they are not anagrams, they cannot be scrambled versions of each other, so return false.
  • Recursive Step: Iterate through all possible split points i from 1 to s1.length() - 1.
    • For each split i, s1 is divided into s1_left = s1.substring(0, i) and s1_right = s1.substring(i).
    • Check two possibilities for s2:
      1. No-swap: s2 is split at the same point i into s2_left and s2_right. Recursively check if isScramble(s1_left, s2_left) AND isScramble(s1_right, s2_right).
      2. Swap: s1_left is compared with the end part of s2 of the same length, and s1_right with the beginning part. Recursively check if isScramble(s1_left, s2.substring(n-i)) AND isScramble(s1_right, s2.substring(0, n-i)).
    • If any of these checks return true, it means a valid scramble is found, so return true.
  • If the loop completes without finding a valid scramble, return false.

Walkthrough

The core of this method is a recursive function isScramble(s1, s2). The base case for the recursion is when the two strings are equal, in which case we return true. A crucial optimization, or pruning step, is to first check if s1 and s2 are anagrams. If their character counts don't match, it's impossible for one to be a scrambled version of the other, so we can immediately return false. For the recursive step, the function iterates through all possible split points of the string s1. For each split, it considers two scenarios based on the problem definition: the two substrings are not swapped, or they are swapped. It then makes recursive calls to check if the corresponding substrings are themselves scrambled. If any of these recursive explorations yield a valid scrambling, the function returns true. If all possibilities are exhausted without success, it returns false.

class Solution {    public boolean isScramble(String s1, String s2) {        if (s1.equals(s2)) {            return true;        }        if (s1.length() != s2.length()) {            return false;        }         // Anagram check        int[] letters = new int[26];        for (int i = 0; i < s1.length(); i++) {            letters[s1.charAt(i) - 'a']++;            letters[s2.charAt(i) - 'a']--;        }        for (int i = 0; i < 26; i++) {            if (letters[i] != 0) {                return false;            }        }         int n = s1.length();        for (int i = 1; i < n; i++) {            // Case 1: No swap            if (isScramble(s1.substring(0, i), s2.substring(0, i)) &&                isScramble(s1.substring(i), s2.substring(i))) {                return true;            }            // Case 2: Swap            if (isScramble(s1.substring(0, i), s2.substring(n - i)) &&                isScramble(s1.substring(i), s2.substring(0, n - i))) {                return true;            }        }        return false;    }}

Complexity

Time

O(n * C_n) ~ O(4^n / n^(3/2))

Space

O(n)

Trade-offs

Pros

  • Simple to understand and implement as it directly models the problem description.

Cons

  • Extremely inefficient due to a massive number of overlapping subproblems.

  • Leads to an exponential time complexity, which will cause a 'Time Limit Exceeded' error for the given constraints.

Solutions

public class Solution { private string s1 ; private string s2 ; private int [,,] f ; public bool IsScramble ( string s1 , string s2 ) { int n = s1 . Length ; this . s1 = s1 ; this . s2 = s2 ; f = new int [ n , n , n + 1 ]; return dfs ( 0 , 0 , n ); } private bool dfs ( int i , int j , int k ) { if ( f [ i , j , k ] != 0 ) { return f [ i , j , k ] == 1 ; } if ( k == 1 ) { return s1 [ i ] == s2 [ j ]; } for ( int h = 1 ; h < k ; ++ h ) { if ( dfs ( i , j , h ) && dfs ( i + h , j + h , k - h )) { f [ i , j , k ] = 1 ; return true ; } if ( dfs ( i , j + k - h , h ) && dfs ( i + h , j , k - h )) { f [ i , j , k ] = 1 ; return true ; } } f [ i , j , k ] = - 1 ; return false ; } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem