1370. Increasing Decreasing String
Problem Description
The given problem requires us to reorder a given string s
following a specific algorithm. The algorithm involves repeatedly picking the smallest and largest characters from the string according to given rules and appending them to form a new result string. The rules for picking characters are as follows:
- Select the smallest character from
s
and append it to the result. - Choose the next-smallest character that is greater than the last appended one and append it.
- Continue with step 2 until no more characters can be picked.
- Select the largest character from
s
and append it to the result. - Choose the next-largest character that is smaller than the last appended one and append it.
- Continue with step 5 until no more characters can be picked.
- Repeat steps 1 to 6 until all characters from
s
have been picked and appended.
The algorithm allows for any occurrence of the smallest or largest character to be chosen if there are multiple.
Intuition
The solution to this problem uses a frequency counter to keep track of how many times each character appears in the string s
. We use an array counter
of length 26 to represent the frequency of each lowercase English letter.
Here's how the solution is constructed:
- Count the frequency of each character in the string
s
and store it incounter
. This allows us to know how many times we need to pick each character during the reordering process. - Initialize an empty list
ans
to build up the result string. - Use a while loop that continues until the length of
ans
matches the length of the input strings
. - Inside the loop, iterate over the
counter
from start to end to append the smallest character (if available) toans
and decrease its count. - Then iterate over the
counter
from end to start to append the largest character (if available) toans
and decrease its count. - The process repeats, alternating between picking the smallest and largest character until all characters are used.
- Convert the list
ans
to a string and return it as the final reordered string.
By following these steps, the algorithm efficiently fulfills the provided reordering rules, and characters are picked in the required order to form the result string.
Solution Approach
The solution implementation utilizes a straightforward approach that involves counting, iterating, and string building.
Here's a detailed walk-through of the implementation using Python:
-
Character Frequency Counting: We start by creating a list of zeroes called
counter
to maintain a count of each letter in the string. The length of the list is 26, one for each letter of the English alphabet. We then iterate over each character of the strings
, and for each character, we find its corresponding index (0 for 'a', 1 for 'b', etc.) by subtracting the ASCII value of 'a' from the ASCII value of the character. We increment the count at this index in thecounter
list.counter = [0] * 26 for c in s: counter[ord(c) - ord('a')] += 1
-
Result String Assembly: We define a list
ans
to accumulate the characters in the order we choose them based on the algorithm rulesāthe resulting string after the reordering will be formed by concatenating the characters in this list. -
Main Loop - Building the Result: We use a
while
loop to repeat the process of picking characters from the strings
according to the described algorithm. The loop will continue until the length ofans
becomes equal to the length of the original strings
, signaling that all characters have been chosen and appended.while len(ans) < len(s): # ...
-
Picking the Smallest Character: Inside the loop, we iterate over the
counter
from the start (0) to the end (25) which corresponds to characters 'a' to 'z'. If the current character's counter is not zero, indicating that it is available to be picked, we append the corresponding character toans
and decrement its count incounter
.for i in range(26): if counter[i]: ans.append(chr(i + ord('a'))) counter[i] -= 1
-
Picking the Largest Character: We do the same for picking the largest character, but in reverse order, iterating over the
counter
from the end (25) to the start (0). Again, if the current character's counter is not zero, we append the corresponding character toans
and decrement its count.for i in range(25, -1, -1): if counter[i]: ans.append(chr(i + ord('a'))) counter[i] -= 1
-
Returning the Result: Finally, after the
while
loop concludes, we join the list of characters inans
using''.join(ans)
to return the final string, which is the original strings
reordered according to the algorithm described.
The above steps translate the problem's algorithm into Python code in a way that is both efficient (since the actions within the loop are simple and fast) and clean, leading to a solution that straightforwardly follows the rules laid out in the problem statement.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a small example to illustrate the solution approach. Suppose our input string s
is "bacab"
.
-
Character Frequency Counting: We count the frequency of every character in the string.
For the string
"bacab"
, the frequency countercounter
would look like this after counting:[2, 2, 1]
, where2
at the first position represents'a'
,2
at the second position is for'b'
, and1
at the third position is for'c'
. -
Result String Assembly: We initialize an empty list
ans
to store the characters as we pick them following the algorithm. -
Main Loop - Building the Result: We start the while loop since
len(ans) < len(s)
, which is5
in this case. -
Picking the Smallest Character: On the first iteration, we look for the smallest character, which is
'a'
. We add'a'
toans
, and thecounter
becomes[1, 2, 1]
. -
Picking the Largest Character: We now pick the largest character, which is
'c'
. After appending'c'
toans
, thecounter
list updates to[1, 2, 0]
. -
Picking the Smallest Character: We pick
'a'
again as it is the next available smallest character. Theans
list becomes['a', 'c', 'a']
andcounter
is[0, 2, 0]
. -
Picking the Largest Character: We need to pick the largest character now, which is
'b'
. After doing so, theans
list is['a', 'c', 'a', 'b']
andcounter
is[0, 1, 0]
. -
Picking the Largest Character: As per our steps, we continue to pick the largest character left, which is still
'b'
, updatingans
to['a', 'c', 'a', 'b', 'b']
andcounter
to[0, 0, 0]
. -
Returning the Result: The while loop exits since
len(ans)
is now equal tolen(s)
. We join the elements ofans
to form the final string. Therefore, the final reordered string is"acabb"
.
By following the steps laid out in the solution approach, we successfully applied the algorithm to the example input and achieved the expected outcome. The method of counting characters, appending the smallest and largest in order, and decrementing their count ensures that the rules of the problem statement are adhered to at every step of the process.
Solution Implementation
1class Solution:
2 def sort_string(self, s: str) -> str:
3 # Initialize a list to keep track of the count of each character in the string
4 char_count = [0] * 26
5
6 # Count the occurrences of each character in the string
7 for char in s:
8 char_count[ord(char) - ord('a')] += 1
9
10 # Initialize a list to build the sorted string
11 sorted_chars = []
12
13 # Continue until the sorted string's length equals the input string's length
14 while len(sorted_chars) < len(s):
15 # Traverse the `char_count` list from start to end and add each character once if it's present
16 for i in range(26):
17 if char_count[i] > 0:
18 sorted_chars.append(chr(i + ord('a')))
19 char_count[i] -= 1 # Decrement the count of the added character
20
21 # Traverse the `char_count` list from end to start and add each character once if it's present
22 for i in range(25, -1, -1):
23 if char_count[i] > 0:
24 sorted_chars.append(chr(i + ord('a')))
25 char_count[i] -= 1 # Decrement the count of the added character
26
27 # Join the list of characters into a string and return it
28 return ''.join(sorted_chars)
29
1class Solution {
2
3 // Method to sort the string in a custom order
4 public String sortString(String s) {
5 // Counter array to hold frequency of each character 'a'-'z'
6 int[] frequency = new int[26];
7 // Fill the frequency array with count of each character
8 for (char ch : s.toCharArray()) {
9 frequency[ch - 'a']++;
10 }
11
12 // StringBuilder to hold the result
13 StringBuilder sortedString = new StringBuilder();
14
15 // Loop until the sortedString's length is less than the original string length
16 while (sortedString.length() < s.length()) {
17 // Loop from 'a' to 'z'
18 for (int i = 0; i < 26; ++i) {
19 // Check if the character is present
20 if (frequency[i] > 0) {
21 // Append the character to sortedString
22 sortedString.append((char) ('a' + i));
23 // Decrement the frequency of appended character
24 frequency[i]--;
25 }
26 }
27 // Loop from 'z' to 'a'
28 for (int i = 25; i >= 0; --i) {
29 // Check if the character is present
30 if (frequency[i] > 0) {
31 // Append the character to sortedString
32 sortedString.append((char) ('a' + i));
33 // Decrement the frequency of appended character
34 frequency[i]--;
35 }
36 }
37 }
38 // Return the resultant sorted string
39 return sortedString.toString();
40 }
41}
42
1class Solution {
2public:
3 // Method to sort the string in a specific pattern
4 string sortString(string s) {
5 // Create a frequency counter for each letter in the alphabet
6 vector<int> frequency(26, 0);
7 for (char c : s) {
8 ++frequency[c - 'a']; // Increment the count of the current letter
9 }
10
11 // Initialize the answer string
12 string result = "";
13
14 // Keep building the result until its size matches the original string size
15 while (result.size() < s.size()) {
16 // Append characters from 'a' to 'z' to the result string if they are present
17 for (int i = 0; i < 26; ++i) {
18 if (frequency[i] > 0) { // Check if the character is present
19 result += (i + 'a'); // Convert index to char and append
20 --frequency[i]; // Decrement the frequency of the used character
21 }
22 }
23
24 // Append characters from 'z' to 'a' to the result string if they are present
25 for (int i = 25; i >= 0; --i) { // Start from 'z'
26 if (frequency[i] > 0) { // Check if the character is present
27 result += (i + 'a'); // Convert index to char and append
28 --frequency[i]; // Decrement the frequency of the used character
29 }
30 }
31 }
32
33 // Return the sorted string
34 return result;
35 }
36};
37
1/**
2 * Sort the string based on the custom order: ascending characters followed by descending characters
3 * @param {string} str - The original string to be sorted.
4 * @return {string} - The sorted string.
5 */
6function sortString(str: string): string {
7 let resultString: string = '';
8 const charMap: Map<string, number> = new Map();
9
10 // Count the occurrences of each character in the string
11 for (let char of str) {
12 charMap.set(char, (charMap.get(char) || 0) + 1);
13 }
14
15 const keys: string[] = Array.from(charMap.keys());
16 keys.sort(); // Sort the keys (characters) in ascending order once
17
18 // Keep constructing the string until the resultString's length equals the input string's length
19 while (resultString.length < str.length) {
20 // Append characters in ascending order to the result string
21 for (let key of keys) {
22 if (charMap.get(key)! > 0) { // Ensure the character count is not zero
23 resultString += key;
24 charMap.set(key, charMap.get(key)! - 1); // Decrement the count in the map
25 }
26 }
27
28 // Append characters in descending order to the result string
29 for (let i = keys.length - 1; i >= 0; i--) {
30 if (charMap.get(keys[i])! > 0) {
31 resultString += keys[i];
32 charMap.set(keys[i], charMap.get(keys[i])! - 1); // Decrement the count in the map
33 }
34 }
35 }
36
37 return resultString;
38}
39
Time and Space Complexity
Time Complexity
The provided Python function sortString
starts with an initial counting pass over the input string s
, incrementing values in counter
which takes O(n)
time, where n
is the length of s
.
After that, it enters a loop that continues until the length of ans
matches that of s
. Within this loop, there are two for-loops: the first iterates in ascending order, the second in descending order. Each of these for-loops iterates over the 26 possible characters (from 'a' to 'z').
For each character, if that character count is non-zero, it is appended to ans
and the count decremented. Since each character in s
is processed exactly once (each is appended and then decremented), and there are two passes for each character (one in ascending and one in descending order), the total count of operations inside the while-loop is 2n
, leading to an additional O(n)
time complexity.
Thus, the time complexity of the entire function is O(n)
.
Space Complexity
The space complexity includes:
- The
counter
array which is always 26 elements long, thus it is a constant spaceO(1)
. - The
ans
list that will eventually grow to be the same size ass
to accommodate all characters, which isO(n)
.
Therefore, the total space complexity is O(n)
, where n
is the length of the input string s
.
Learn more about how to find time and space complexity quickly using problem constraints.
Which algorithm should you use to find a node that is close to the root of the tree?
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Donāt Miss This!