Shuffle String - Video Solutions

Problem Overview: You are given a string s and an integer array indices of the same length. Each position in indices tells you where the character at that position in s should appear in the final string. The task is to reconstruct the shuffled string after applying all index mappings.

Approach 1: Array Construction (O(n) time, O(n) space)

The direct solution builds a new character array of size n. Iterate through the string once, and for each index i, place s[i] into position indices[i] of the result array. After the loop finishes, convert the array back to a string. The key insight is that indices already tells you the exact final position of every character, so there is no need for searching or shifting. Every element is processed exactly once, giving O(n) time complexity and O(n) extra space for the result array.

This approach is clean, readable, and works consistently across languages. It relies on basic operations like array indexing and iteration, which makes it ideal when working with arrays and strings. Most production code would use this version because clarity outweighs the small extra memory cost.

Approach 2: In-place Array Modification (O(n) time, O(1) extra space)

You can avoid allocating a separate array by performing swaps until each character reaches its correct index. Iterate through the array, and while indices[i] != i, swap the character at position i with the character at position indices[i]. At the same time, swap the corresponding values in the indices array so the mapping stays consistent. Each swap moves at least one element into its correct position, so the total work remains linear.

This technique treats the problem as a permutation correction. The indices array describes a permutation of positions, and swaps gradually fix cycles in that permutation. Because all rearrangement happens inside the existing arrays, the algorithm runs in O(n) time with O(1) extra space. The tradeoff is slightly more complex logic and careful swap handling.

Recommended for interviews: The array construction approach is what most interviewers expect first. It demonstrates that you quickly recognized the direct mapping between source and destination indices. After presenting it, mentioning the in-place permutation idea shows deeper understanding of array manipulation and space optimization. Interviewers typically accept the O(n) time, O(n) space solution as optimal because it keeps the code simple and avoids unnecessary complexity.