Scramble String

HardDynamic Programminginterval dp

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

A string s can be scrambled by the following recursive process: - If s has length 1, stop. - Otherwise split s at any position into two non-empty parts x and y (so s = x + y). Then choose to keep them in order (x + y) or swap them (y + x), and independently scramble each part again with this same process. Given two strings s1 and s2 of equal length, return true if s2 can be produced by scrambling s1, and false otherwise. A string is always a scramble of itself.

Examples

Input: s1 = "great", s2 = "rgeat"
Output: true
Split "great" into "gr" + "eat", keep the order, then split "gr" into "g" + "r" and swap to get "rg". The result is "rgeat".
Input: s1 = "abcde", s2 = "caebd"
Output: false
No sequence of splits and swaps turns "abcde" into "caebd".
Input: s1 = "a", s2 = "a"
Output: true
A single character is trivially a scramble of itself.

Constraints

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

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More interval dp problems