algoadvance

Leetcode 1528. Shuffle String Sure, let’s break down the problem:

Problem Statement

You are given a string s and an integer array indices of the same length. The string s will be rearranged such that the character at the ith position moves to indices[i] in the shuffled string. Return the shuffled string.

Example

Input: s = "code", indices = [3, 1, 2, 0]
Output: "edoc"
Explanation: As the indices are [3, 1, 2, 0], the characters of s will be moved to the respective positions: "c" -> 3, "o" -> 1, "d" -> 2, "e" -> 0. Thus, the output is "edoc".

Clarifying Questions

  1. Are the characters in the string s unique?
    • No, the characters may not be unique.
  2. Are there any constraints on the length of the string s?
    • The length of the string can be up to 100.

Let’s proceed to the strategy and code.

Strategy

  1. Initialize a Result String: Create a result string result of the same length as s and initialize it with empty spaces or any placeholder character.
  2. Rearrange Characters: Iterate through the input string and place each character at the target index specified in the indices array.
  3. Build the Output: Join the characters to form the final shuffled string.

Code

Here’s the C++ code implementation:

#include <iostream>
#include <vector>
#include <string>

std::string restoreString(const std::string& s, const std::vector<int>& indices) {
    int n = s.size();
    std::string result(n, ' '); // Initialize a result string with spaces of the same length as s

    for (int i = 0; i < n; ++i) {
        result[indices[i]] = s[i]; // Place each character at the correct position
    }

    return result; // Return the rearranged result
}

int main() {
    std::string s = "code";
    std::vector<int> indices = {3, 1, 2, 0};

    std::string shuffled = restoreString(s, indices);
    std::cout << "Shuffled string: " << shuffled << std::endl;

    return 0;
}

Time Complexity

The time complexity of this solution is:

Space Complexity

The space complexity is also:

Feel free to ask any further clarifying questions or for additional help!

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI