Mutating counts without cleanup
Wrong move: Zero-count keys stay in map and break distinct/count constraints.
Usually fails on: Window/map size checks are consistently off by one.
Fix: Delete keys when count reaches zero.
Build confidence with an intuition-first walkthrough focused on hash map fundamentals.
You are given a string s. Reorder the string using the following algorithm:
s and append it to the result.s that is greater than the last appended character, and append it to the result.s and append it to the result.s that is smaller than the last appended character, and append it to the result.s have been removed.If the smallest or largest character appears more than once, you may choose any occurrence to append to the result.
Return the resulting string after reordering s using this algorithm.
Example 1:
Input: s = "aaaabbbbcccc" Output: "abccbaabccba" Explanation: After steps 1, 2 and 3 of the first iteration, result = "abc" After steps 4, 5 and 6 of the first iteration, result = "abccba" First iteration is done. Now s = "aabbcc" and we go back to step 1 After steps 1, 2 and 3 of the second iteration, result = "abccbaabc" After steps 4, 5 and 6 of the second iteration, result = "abccbaabccba"
Example 2:
Input: s = "rat" Output: "art" Explanation: The word "rat" becomes "art" after re-ordering it with the mentioned algorithm.
Constraints:
1 <= s.length <= 500s consists of only lowercase English letters.Problem summary: You are given a string s. Reorder the string using the following algorithm: Remove the smallest character from s and append it to the result. Remove the smallest character from s that is greater than the last appended character, and append it to the result. Repeat step 2 until no more characters can be removed. Remove the largest character from s and append it to the result. Remove the largest character from s that is smaller than the last appended character, and append it to the result. Repeat step 5 until no more characters can be removed. Repeat steps 1 through 6 until all characters from s have been removed. If the smallest or largest character appears more than once, you may choose any occurrence to append to the result. Return the resulting string after reordering s using this algorithm.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Hash Map
"aaaabbbbcccc"
"rat"
Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #1370: Increasing Decreasing String
class Solution {
public String sortString(String s) {
int[] cnt = new int[26];
int n = s.length();
for (int i = 0; i < n; ++i) {
cnt[s.charAt(i) - 'a']++;
}
StringBuilder sb = new StringBuilder();
while (sb.length() < n) {
for (int i = 0; i < 26; ++i) {
if (cnt[i] > 0) {
sb.append((char) ('a' + i));
--cnt[i];
}
}
for (int i = 25; i >= 0; --i) {
if (cnt[i] > 0) {
sb.append((char) ('a' + i));
--cnt[i];
}
}
}
return sb.toString();
}
}
// Accepted solution for LeetCode #1370: Increasing Decreasing String
func sortString(s string) string {
cnt := [26]int{}
for _, c := range s {
cnt[c-'a']++
}
n := len(s)
ans := make([]byte, 0, n)
for len(ans) < n {
for i := 0; i < 26; i++ {
if cnt[i] > 0 {
ans = append(ans, byte(i)+'a')
cnt[i]--
}
}
for i := 25; i >= 0; i-- {
if cnt[i] > 0 {
ans = append(ans, byte(i)+'a')
cnt[i]--
}
}
}
return string(ans)
}
# Accepted solution for LeetCode #1370: Increasing Decreasing String
class Solution:
def sortString(self, s: str) -> str:
cnt = Counter(s)
cs = ascii_lowercase + ascii_lowercase[::-1]
ans = []
while len(ans) < len(s):
for c in cs:
if cnt[c]:
ans.append(c)
cnt[c] -= 1
return "".join(ans)
// Accepted solution for LeetCode #1370: Increasing Decreasing String
struct Solution;
impl Solution {
fn sort_string(s: String) -> String {
let mut count: Vec<usize> = vec![0; 26];
let mut n = s.len();
for c in s.chars() {
count[(c as u8 - b'a') as usize] += 1;
}
let mut direction = true;
let mut res = "".to_string();
while n > 0 {
if direction {
for i in 0..26 {
if count[i] > 0 {
count[i] -= 1;
n -= 1;
res.push((b'a' + i as u8) as char);
}
}
} else {
for i in (0..26).rev() {
if count[i] > 0 {
count[i] -= 1;
n -= 1;
res.push((b'a' + i as u8) as char);
}
}
}
direction = !direction;
}
res
}
}
#[test]
fn test() {
let s = "aaaabbbbcccc".to_string();
let res = "abccbaabccba".to_string();
assert_eq!(Solution::sort_string(s), res);
let s = "rat".to_string();
let res = "art".to_string();
assert_eq!(Solution::sort_string(s), res);
let s = "leetcode".to_string();
let res = "cdelotee".to_string();
assert_eq!(Solution::sort_string(s), res);
let s = "ggggggg".to_string();
let res = "ggggggg".to_string();
assert_eq!(Solution::sort_string(s), res);
let s = "spo".to_string();
let res = "ops".to_string();
assert_eq!(Solution::sort_string(s), res);
}
// Accepted solution for LeetCode #1370: Increasing Decreasing String
function sortString(s: string): string {
const cnt: number[] = Array(26).fill(0);
for (const c of s) {
++cnt[c.charCodeAt(0) - 'a'.charCodeAt(0)];
}
const ans: string[] = [];
while (ans.length < s.length) {
for (let i = 0; i < 26; ++i) {
if (cnt[i]) {
ans.push(String.fromCharCode(i + 'a'.charCodeAt(0)));
--cnt[i];
}
}
for (let i = 25; i >= 0; --i) {
if (cnt[i]) {
ans.push(String.fromCharCode(i + 'a'.charCodeAt(0)));
--cnt[i];
}
}
}
return ans.join('');
}
Use this to step through a reusable interview workflow for this problem.
For each element, scan the rest of the array looking for a match. Two nested loops give n × (n−1)/2 comparisons = O(n²). No extra space since we only use loop indices.
One pass through the input, performing O(1) hash map lookups and insertions at each step. The hash map may store up to n entries in the worst case. This is the classic space-for-time tradeoff: O(n) extra memory eliminates an inner loop.
Review these before coding to avoid predictable interview regressions.
Wrong move: Zero-count keys stay in map and break distinct/count constraints.
Usually fails on: Window/map size checks are consistently off by one.
Fix: Delete keys when count reaches zero.