algoadvance

Leetcode 791. Custom Sort String Sure, let’s go through this problem step-by-step. Here’s the structure of our discussion:

  1. Problem Statement
  2. Clarifying Questions
  3. Strategy
  4. Code
  5. Time Complexity

Problem Statement

Given two strings order and s. order is a permutation of the English alphabet. Rearrange the characters of s such that they match the order that order was sorted in. Any character in s that does not appear in order should be sorted at the end of the output string in their original order.

Example:

Input: order = "cba", s = "abcd"
Output: "cbad"
Explanation: "c", "b", and "a" appear in 'order', so they are sorted like "cba". "d" is not in 'order', so it remains at the end.

Clarifying Questions

  1. Q: Can order contain all the characters of the alphabet? A: No, order is a permutation of a subset of the alphabet.

  2. Q: What should be done with characters in s not appearing in order? A: They should retain their relative positions but appear at the end of the sorted result.

  3. Q: Are there any constraints on the size of order and s? A: Yes. The strings order and s will have lengths in the range [1, 1000].

Strategy

  1. Counting characters in s: We’ll use a hashmap to count the occurrences of each character in s.
  2. Building the result based on order: We’ll iterate over order and append characters to the result string based on the count we have stored.
  3. Appending remaining characters: Any characters in s that are not in order will be appended to the end of the result in the order they appear in s.

Code

Here’s how to implement the strategy in C++:

#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;

string customSortString(string order, string s) {
    unordered_map<char, int> count;
    
    // Count each character in s
    for (char c : s) {
        count[c]++;
    }
    
    // Construct the result string based on the order
    string result;
    for (char c : order) {
        if (count.find(c) != count.end()) {
            result.append(count[c], c);
            count.erase(c);
        }
    }
    
    // Append any remaining characters not present in order
    for (char c : s) {
        if (count.find(c) != count.end()) {
            result.append(count[c], c);
            count.erase(c);
        }
    }
    
    return result;
}

// Example usage
int main() {
    string order = "cba";
    string s = "abcd";
    cout << customSortString(order, s) << endl; // Output: "cbad"
    return 0;
}

Time Complexity

This approach ensures that characters in s are rearranged as per the order and maintains the correct positions for characters not in order.

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