🌱 Keegan's Digital Garden

1528. Shuffle String

2 min read

📝 Problem Details

💭What Were My Initial Thoughts?

1. This problem requires rearranging the characters of a string `s` based on the order provided in the `indices` array.
2. A simple approach is to use a temporary data structure (e.g., a vector or a new string) to "map" each character of `s` to its new position given by `indices`.
3. Sorting can also be a valid approach, pairing the indices with their corresponding characters, but a direct mapping is more efficient.

🤔What Did I Struggle With?

~

💡 Explanation of Solution

1. **Approach (v1): Using Sorting**
   - Pair each index in `indices` with its corresponding character from `s`.
   - Sort these pairs by the index.
   - Reconstruct the resulting string from the sorted pairs.
   - Complexity: Sorting the pairs adds overhead, making this approach less optimal.

2. **Approach (v2): Direct Mapping**
   - Create a new string `result` initialized to the same size as `s`.
   - Use the `indices` array to directly place each character from `s` into its correct position in `result`.
   - This avoids the need for sorting and is more efficient.

3. **Steps for Both Approaches:**
   - Parse the `indices` array to determine the new position of each character in `s`.
   - Rearrange the characters of `s` based on this mapping.
   - Return the rearranged string.

4. **Why v2 is Preferred**:
   - It directly maps characters to their positions in `O(n)` time.
   - Avoids the overhead of sorting, making it faster and more memory-efficient.

⌛ Complexity Analysis

1. **Time Complexity:**
   - v1 (Sorting): `O(n log n)` for sorting the index-character pairs.
   - v2 (Direct Mapping): `O(n)` as it iterates over `indices` to directly map characters.
   
2. **Space Complexity:**
   - v1: `O(n)` for storing the index-character pairs.
   - v2: `O(n)` for the resulting string.
   - Both approaches require linear space for the result string.

💻 Implementation of Solution v.1

class Solution {
public:
    string restoreString(string s, vector<int>& indices) {
        vector<pair<int, char>> mappings;
 
        for(int i=0; i < indices.size(); i++) {
            mappings.push_back({indices[i], s[i]});
        }
 
        sort(mappings.begin(), mappings.end());
 
        string result;
 
        for(int i=0; i < indices.size(); i++) {
            result += mappings[i].second;
        }
        
        return result;
    }
};

💻 Implementation of Solution v.2

class Solution {
public:
    string restoreString(string s, vector<int>& indices) {
        string result = s;
 
        for(int i=0; i < indices.size(); i++) {
            result[indices[i]] = s[i];
        }
 
        return result;
    }
};

Graph View