791. Custom Sort String

MediumHash TableStringSorting

Problem Description

The problem presents two strings - order and s. The string order contains unique characters that follow a custom sorted order. The task is to rearrange the characters in string s such that they follow the same sorting order as the characters in order. It is important to preserve the relative order of characters as they appear in order. If s contains characters that are not present in order, these characters should be placed at the end of the result string in any order. The problem requires us to output any valid permutation of s that meets this criterion.

Intuition

The intuition behind the solution is to respect the precedence of characters as given in order. Since order dictates the relative ordering of characters, the solution should build the resulting string by appending characters in the order they appear in order.

The first step is to count the occurrences of each character in s. We use this information to determine how many times each character should appear in the resulting string. We iterate over order, and for each character, we append it to the result as many times as it occurs in s (using the count we stored earlier).

We then set the count of those characters to zero to indicate that we have already placed those characters in the result. Finally, if there are any characters left in s that were not in order, we append them to the end of the result string. Since the order of these leftover characters doesn't matter, we simply append them in any order they occur.

By doing this, we ensure that the characters are sorted according to the order specified by order, and if s has extra characters not in order, they are just tacked on at the end.

Learn more about Sorting patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What's the output of running the following function using the following tree as input?

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12

1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18

1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

1 2 3 6 x x1 2 3 x x x 6 x x1 2 6 x x x 3 x x

I don’t know

Solution Approach

The solution approach involves two primary components to achieve the desired ordering of characters: counting occurrences and ordering as per order.

Counting Occurrences: We utilize the Counter class from Python's collections module to create a frequency map, cnt, which tracks the number of occurrences of each character in s. This gives us a dictionary where the keys are the characters from s, and the values are the number of times they appear in s.
Ordering as Per order: We initialize an empty list called ans which will hold the characters in the new order. We iterate through each character c in order:
- Append the character c to ans, multiplied by its count from cnt (which is cnt[c]). This step ensures that if a character c is supposed to appear n times, it's added n times consecutively to ans.
- Set cnt[c] to 0 to denote that we've accounted for all occurrences of c as specified by order.
Handling Remaining Characters: After processing all characters in order, there might be characters left in s that were not present in order. To handle such characters, we:
- Iterate through the remaining items in cnt.
- For every character c and its count v in cnt, append the character c to ans, multiplied by its count v. This ensures that characters not in order are placed at the end of ans.
Building the Final String: We use ''.join(ans) to convert the list of characters ans into a string which is the final sorted string according to the custom order specified by order.

By following this process, we ensure that all characters in order take precedence and are arranged as per their ordering in order. Characters not found in order follow an ad-hoc order at the end of the sorted string. The solution abides by the problem constraints and provides a correctly ordered permutation of the string s.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Example Walkthrough

Let's consider a small example where order = "cba" and s = "abcdabc". We want to sort the string s such that it follows the order given by order and any extra characters are placed at the end.

Step 1: Counting Occurrences: We count the occurrences of each character in s. The count will look like this: cnt = {'a': 2, 'b': 2, 'c': 2, 'd': 1}.
Step 2: Ordering as Per order: Initialize ans as an empty list, where we will append our characters.
1. For character c in order, which is 'c', cnt[c] is 2. We append 'c' twice to ans, making it ['c', 'c'], and set cnt['c'] to 0.
2. Next is 'b' in order. cnt['b'] is 2. We append 'b' twice to ans, which becomes ['c', 'c', 'b', 'b'], and set cnt['b'] to 0.
3. Then for 'a' in order, cnt['a'] is 2. We append 'a' twice to ans, now ans is ['c', 'c', 'b', 'b', 'a', 'a'], and set cnt['a'] to 0.
Step 3: Handling Remaining Characters: We have 'd' left in cnt with a count of 1, which was not in order. We append 'd' once to ans, resulting in ['c', 'c', 'b', 'b', 'a', 'a', 'd'].
Step 4: Building the Final String: Join the characters in ans to get the final sorted string: 'ccbbadd'.

The result 'ccbbadd' is one valid permutation of s where the order 'cba' is followed, and the character 'd' (which is not in order) is placed at the end.

Solution Implementation

1from collections import Counter
2
3class Solution:
4    def customSortString(self, order: str, s: str) -> str:
5        # Count the occurrences of each character in the string s
6        char_count = Counter(s)
7
8        # Initialize the answer as an empty list; it will store the sorted characters
9        sorted_characters = []
10
11        # Add characters to the sorted_characters list following the order specified.
12        # Multiply the character by its count to add it that many times.
13        for char in order:
14            sorted_characters.append(char * char_count[char])
15            # Set the count for this character to 0 since it's been handled
16            char_count[char] = 0
17
18        # Add remaining characters that were not in 'order' to the list.
19        # These are added at the end in their original order of occurrence.
20        for char, count in char_count.items():
21            sorted_characters.append(char * count)
22
23        # Join all the characters in the sorted_characters list to form the sorted string
24        return ''.join(sorted_characters)
25

1class Solution {
2    public String customSortString(String order, String str) {
3        // Create an array to count each character's frequency in 'str'.
4        int[] frequency = new int[26];
5      
6        // Iterate through the 'str' to populate the character frequencies.
7        for (int i = 0; i < str.length(); ++i) {
8            frequency[str.charAt(i) - 'a']++;
9        }
10      
11        // Use StringBuilder to build the sorted string for efficient string manipulation.
12        StringBuilder sortedStringBuilder = new StringBuilder();
13      
14        // Iterate through the 'order' string.
15        for (int i = 0; i < order.length(); ++i) {
16            char currentChar = order.charAt(i);
17          
18            // Append the current character from 'order' to the sorted string
19            // as many times as it appears in 'str'.
20            while (frequency[currentChar - 'a'] > 0) {
21                sortedStringBuilder.append(currentChar);
22                frequency[currentChar - 'a']--;
23            }
24        }
25      
26        // Append the remaining characters that were not in 'order' to the sorted string.
27        for (int i = 0; i < 26; ++i) {
28            while (frequency[i] > 0) {
29                sortedStringBuilder.append((char) ('a' + i));
30                frequency[i]--;
31            }
32        }
33      
34        // Return the final sorted string.
35        return sortedStringBuilder.toString();
36    }
37}
38

1class Solution {
2public:
3    string customSortString(string order, string str) {
4        // Create an array to keep count of each character's occurrence in str
5        int charCounts[26] = {0};
6      
7        // Fill the array with the counts of each character
8        for (char& c : str) {
9            charCounts[c - 'a']++;
10        }
11
12        // This string will store the result
13        string sortedStr;
14
15        // Iterate over the 'order' string and append the characters to 'sortedStr' in the order they appear
16        for (char& c : order) {
17            while (charCounts[c - 'a']-- > 0) {
18                sortedStr += c;
19            }
20        }
21
22        // Append characters that did not appear in 'order' to the end of 'sortedStr', in their original order
23        for (int i = 0; i < 26; ++i) {
24            // Check if the character is present in 'str' and was not included via 'order'
25            if (charCounts[i] > 0) {
26                // Append the character (i + 'a') 'charCounts[i]' times to the 'sortedStr'
27                sortedStr += string(charCounts[i], i + 'a');
28            }
29        }
30
31        // Return the custom sorted string
32        return sortedStr;
33    }
34};
35

1function customSortString(order: string, str: string): string {
2    // Function to convert a character to its alphabet index (0 for 'a', 1 for 'b', etc.)
3    const charToIndex = (char: string) => char.charCodeAt(0) - 'a'.charCodeAt(0);
4
5    // Initialize an array to keep track of the count of each character in str
6    const charCount = new Array(26).fill(0);
7    // Populate the character count array
8    for (const char of str) {
9        charCount[charToIndex(char)]++;
10    }
11
12    // Initialize an array to construct the final sorted string
13    const sortedChars: string[] = [];
14
15    // Add characters to the sortedChars array in the order specified by 'order'
16    for (const char of order) {
17        const index = charToIndex(char);
18        sortedChars.push(char.repeat(charCount[index])); // Add ordered characters
19        charCount[index] = 0; // Reset the count since these characters are now processed
20    }
21
22    // Add the remaining characters that were not specified in 'order', in lexicographical order
23    for (let i = 0; i < 26; i++) {
24        if (charCount[i] === 0) continue; // Skip characters with a count of zero
25        sortedChars.push(
26            String.fromCharCode('a'.charCodeAt(0) + i).repeat(charCount[i])
27        );
28    }
29
30    // Join the array of sorted characters into a single string and return it
31    return sortedChars.join('');
32}
33

Not Sure What to Study? Take the 2-min Quiz：

What are the most two important steps in writing a depth first search function? (Select 2)

Determine state to pass down to recursive function callDetermine return valueDetermine how many recursive calls will be madeTracing the recursive calls

Time and Space Complexity

Time Complexity

The time complexity of the function can be analyzed in two main steps involved in the customSortString method:

Counting occurrences of all characters in the input string s. This is done with the Counter collection from Python's collections module, which will take O(N) time, where N is the length of the string s.
Constructing the sorted string:
- For each character in order, it appends that character to ans as many times as it occurs in s. This process takes O(M) time, where M is the length of the order string, assuming that appending to the list and setting the count to zero are constant time operations.
- Furthermore, it iterates over the items in cnt to append the remaining characters. This iteration will, again, take at most O(N) time since the number of keys in cnt cannot exceed the number of characters in s.

Putting this together, the total time complexity is O(N) + O(M) + O(N), which simplifies to O(N + M).

Space Complexity

The space complexity of the given code is influenced by the following:

The Counter object cnt, which stores a frequency count of characters in s. In the worst case, if all characters in s are unique, the space taken would be O(N).
The ans list, which collects the sorted characters. In the worst case, when no characters are duplicated in s, this would again require O(N) space.

Therefore, the maximum space requirement is for storing the Counter object and the output list, which adds up to O(N) space complexity.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which two pointer technique does Quick Sort use?

Fast-slow pointersTwo pointers moving in opposite directionSliding windowPrefix sum

I don’t know

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

791. Custom Sort String

Problem Description

Intuition

Solution Approach

Example Walkthrough

Solution Implementation

Time and Space Complexity

Time Complexity

Space Complexity

Recommended Readings