Shuffle a String by Swapping Tree Children
Updated
Problem statement
You are given two strings s1 and s2 of the same length.
Build a binary tree from s1. The root holds all of s1. Any node that holds two or more letters can be cut into two non-empty parts at any position you like: the left part becomes its left child and the right part becomes its right child. A node with one letter is a leaf. You choose every cut.
A shuffle picks one node that has two children and swaps them, so that the node now reads as its right part followed by its left part. You may shuffle any number of nodes, including none. Reading the leaves from left to right then gives the new string.
Return true if some choice of cuts and shuffles turns s1 into s2. Otherwise, return false.
Function
canShuffleInto(s1: String, s2: String) → booleanExamples
Example 1
s1 = "great"s2 = "taerg"return = trueCut great into gr and eat, and swap them.
Cut eat into e and at, and swap them. Then cut at into a and t, and swap those too. Now eat reads tae.
Cut gr into g and r, and swap them to get rg.
The leaves now read tae followed by rg, which is taerg.
Example 2
s1 = "lamp"s2 = "palm"return = trueCut lamp into lam and p, and swap them, so p comes first.
Cut lam into la and m without a swap, and cut la into l and a with a swap. Now lam reads alm.
The result is p followed by alm, which is palm.
Example 3
s1 = "lamp"s2 = "aplm"return = falseBoth strings use the same letters, but no tree works.
Whatever the first cut of lamp is, the result is one shuffled part followed by the other. So s2 must start with a block that holds exactly the letters of one part.
- Cut
l|amp:s2would start withlor end withl. It does neither. - Cut
la|mp: the first two letters ofs2would belanda, ormandp. They areaandp. - Cut
lam|p:s2would start withpor end withp. It does neither.
So the answer is false.
Constraints
1 <= s1.length <= 40s2.length == s1.lengths1ands2contain only lowercase English letters.
More Nutanix Online Assessment questions
- Good SubsequencesOA · Seen Jul 2026
- Min Cost to Connect All PointsOA · Seen Jun 2026
- Digit Changes for a Multiple of 9OA · Seen Aug 2025
- Gas Station Loop StartOA · Seen Aug 2025
- Number of Players (for MTS2)OA · Seen Oct 2024
- Work Schedules (for MTS2)OA · Seen Oct 2024
- Minimum Operations to Convert ArrayOA · Seen Apr 2024
- No Adjacent CharactersOA · Seen Apr 2024
- Build a BST From a ListOA · Seen Nov 2022
- Delete Even-Valued Nodes From a Linked ListOA · Seen Nov 2022
Similar questions at other companies
- Maximum Crayon Removal ScoreWells Fargo · OAWells Fargo interview questions
- Scramble StringExpedia · ONSITE INTERVIEWExpedia interview questions
- Edit DistanceAstrotalk · PHONE SCREEN
- Validate a Palindrome After Limited DeletionsMeta · PHONE SCREEN · ONSITE INTERVIEWMeta interview questions
- Minimum Dictionary SegmentsGoogle · PHONE SCREENGoogle interview questions
- Wildcard Pattern MatchingMicrosoft · ONSITE INTERVIEWMicrosoft interview questions
- Every Result of Grouping an ExpressionC3.ai · ONSITE INTERVIEWC3.ai interview questions
- Lexicographically Smallest Grid Path with One Letter ChangeInfosys · OAInfosys interview questions
- Minimum Merge ConflictsAmazon · OA
- String Formation (Also for AI/ML Software Engineer Intern :)Snowflake · OASnowflake interview questions