Scramble String

Hard

Google

2 views

Topics:

StringsDynamic ProgrammingRecursion

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.

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.

Scramble String

Hard

Google

2 views

Topics:

StringsDynamic ProgrammingRecursion

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.

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.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input strings s1 and s2 have different lengths? If so, what should the function return?
Are the input strings s1 and s2 guaranteed to contain only lowercase English letters?
Can the input strings be empty or null? If so, what should the function return?
To clarify the definition of "scramble," does it involve partitioning the string into *two non-empty* parts, or can one part be empty?
If multiple scrambling combinations are possible that result in s2, do I need to find all of them, or is it sufficient to determine if *any* valid scramble exists?

Brute Force Solution

Approach

The brute-force approach to determine if one string is a scrambled version of another involves exploring every possible way to cut and rearrange the first string. We essentially generate all possible scrambled versions of the first string and then check if any of these match the second string. If even one match is found, we know they are scrambled versions of each other.

Here's how the algorithm would work step-by-step:

Consider all the ways you can split the first string into two parts.
For each of those splits, you can either swap the order of the parts or keep them in the same order.
Each different arrangement of the two parts creates a new, potentially scrambled version of the string.
Repeat this splitting and rearranging process for each of the parts you created in the earlier steps. Keep doing this until you can't split the parts any further.
By repeating this process on the parts of the string, you are generating all possible scrambled versions of the initial string.
Once you have a possible scrambled version, compare it directly to the second string to see if they match exactly.
Keep generating and comparing scrambled versions until you find a match, or until you've exhausted every possible way to scramble the first string.
If you find a match, then the strings are scrambled versions of each other. If you get through every possibility and never find a match, then the strings are not scrambled versions of each other.

Code Implementation

def is_scramble_string_brute_force(string1, string2):
    if len(string1) != len(string2):
        return False

    if string1 == string2:
        return True

    if sorted(string1) != sorted(string2):
        return False

    string_length = len(string1)

    # Iterate through all possible split points
    for i in range(1, string_length):

        #Consider no swap
        if (is_scramble_string_brute_force(string1[:i], string2[:i]) and\
            is_scramble_string_brute_force(string1[i:], string2[i:])): 
            return True

        #Consider swap
        #This checks if a scramble exists.
        if (is_scramble_string_brute_force(string1[:i], string2[string_length-i:]) and\
            is_scramble_string_brute_force(string1[i:], string2[:string_length-i])):
            return True

    return False

Big(O) Analysis

Time Complexity

O(n!) – The brute force approach involves exploring all possible ways to split the first string of length n. At each level of recursion, we can split the string in n-1 ways. For each of these splits, we can either swap or not swap the two parts. This leads to a decision tree where the number of possible scrambled versions grows extremely quickly, roughly proportional to the number of permutations. The number of permutations is n!, therefore the time complexity is approximately O(n!).

Space Complexity

O(N^2) – The brute-force approach described involves recursion to explore all possible splits and rearrangements of the input string. The depth of this recursion can be at most N, where N is the length of the string. At each level of the recursion, string slicing operations (implied in the splitting) can create new string objects up to a size of N. Since there could be up to N levels and slicing at each level is a cost of O(N), and intermediate results are stored at each recursive call in the call stack, the space complexity is proportional to N * N, or N^2, due to the recursive call stack and temporary string allocations at each level. Therefore, the auxiliary space complexity is O(N^2).

Optimal Solution

Approach

The goal is to figure out if one string can be rearranged to look like another by swapping parts of it. The best way to do this is to check if breaking both strings into smaller identical parts is possible, because if you can break them into equivalent smaller pieces, it means they're scrambled versions of each other.

Here's how the algorithm would work step-by-step:

First, make sure the two strings have the exact same letters, just in a different order. If not, they can't be scrambled versions of each other.
If the strings are short enough, just check every possible way to split and swap them, to see if one string can become the other.
If the strings are long, use a clever trick: imagine cutting each string in the same place. Now, there are two possibilities: either the left part of the first string matches the left part of the second string, and the right parts also match, or the left part of the first string matches the right part of the second string, and vice versa.
If *either* of those two possibilities is true, the strings are scrambled versions of each other. If *neither* is true, try cutting the strings in a different place.
To check if the left/right parts match, use this same method on each of those smaller parts. Keep breaking down the problem into smaller and smaller pieces until you get to short strings that you can easily compare.
If, at any point, you find a way to break the strings down into matching parts, you know they are scrambled versions of each other, and you can stop looking.
If you've tried every possible way to break down the strings and you never find a match, then they are not scrambled versions of each other.

Code Implementation

def is_scramble(first_string, second_string):
    if len(first_string) != len(second_string):
        return False

    if sorted(first_string) != sorted(second_string):
        return False

    string_length = len(first_string)

    if string_length <= 3:
        return sorted(first_string) == sorted(second_string)

    for i in range(1, string_length):
        # Check both possibilities: swap or no swap.
        if (is_scramble(first_string[:i], second_string[:i]) and\
            is_scramble(first_string[i:], second_string[i:])): 
            return True

        # Here, we're checking the swapped possibility
        if (is_scramble(first_string[:i], second_string[string_length - i:]) and\
            is_scramble(first_string[i:], second_string[:string_length - i])):
            return True

    return False

Big(O) Analysis

Time Complexity

O(n^4) – The primary driver of the time complexity is the recursive nature of the solution combined with the iterations needed to split the strings. For a string of length n, we iterate from 1 to n-1 to find potential split points. For each split point, we recursively call the function on two pairs of substrings. In the worst-case scenario, where the string can be split in numerous ways and the recursion explores all possibilities, we have a complexity akin to O(n) for the splitting loop multiplied by the cost of the recursive calls. Each recursive call can further split the string, leading to a complexity of O(n^2) for a single level of recursion. Considering the depth of the recursion can also be up to n, in the worst case the complexity climbs up to O(n^4).

Space Complexity

O(N^2) – The primary driver of space complexity is the recursive calls. In the worst-case scenario, the recursion depth can reach N, where N is the length of the input strings. For each recursive call, string slicing creates new string objects, resulting in potentially many substrings stored in memory, up to O(N^2) in total. Specifically, we can have up to N levels of recursion and each level creates approximately N substrings of varying lengths from the input. Therefore the auxiliary space complexity is O(N^2).

Edge Cases

Case	How to Handle
Null or empty strings s1 or s2	Return true if both are null/empty, false if one is null/empty while the other is not; otherwise, throw IllegalArgumentException.
Strings s1 and s2 have different lengths	Return false immediately, as scrambled strings must have equal length.
Strings s1 and s2 are equal	Return true immediately, as identical strings are trivially scrambled versions of each other.
Strings s1 and s2 have different character counts	Return false if character counts differ, as any scrambling preserves character counts.
Strings with very long length leading to stack overflow during recursive calls.	Consider using a DP approach instead of recursion to avoid stack overflow errors.
String containing only 1 character.	Return true if both strings have same single character, false otherwise.
Very deep recursion calls due to string characteristics.	Memoize intermediate results (subproblems) to avoid redundant calculations and improve performance.
Integer overflow when calculating string hash values (if using hashing for comparison).	Use modulo operator with a large prime number or choose a hashing algorithm that avoids overflow.