LeetCode 1370: Increasing Decreasing String (Counting + Zigzag Alphabet Scan)
LeetCode 1370StringCountingToday we solve LeetCode 1370 - Increasing Decreasing String.
Source: https://leetcode.com/problems/increasing-decreasing-string/
English
Problem Summary
Given a string s, repeatedly pick the smallest available characters in increasing order, then the largest available characters in decreasing order, until all characters are used. Return the constructed string.
Key Insight
Only lowercase English letters exist, so we can count frequencies with a size-26 array. Then we simulate the required process by scanning a → z, then z → a, appending one character when available.
Algorithm
- Count each character frequency in cnt[26].
- While result length is smaller than s.length():
1) for i = 0..25, if cnt[i] > 0, append letter and decrement.
2) for i = 25..0, do the same.
- Return the built string.
Complexity Analysis
Let n be the length of s.
Time: O(26 * rounds), effectively O(n).
Space: O(26) = O(1).
Common Pitfalls
- Forgetting to alternate ascending and descending scans.
- Appending multiple copies in one pass when the rule asks for at most one per letter per direction pass.
- Using full sort + repeated deletion, which is slower and harder to manage.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public String sortString(String s) {
int[] cnt = new int[26];
for (char c : s.toCharArray()) {
cnt[c - 'a']++;
}
StringBuilder ans = new StringBuilder();
while (ans.length() < s.length()) {
for (int i = 0; i < 26; i++) {
if (cnt[i] > 0) {
ans.append((char)('a' + i));
cnt[i]--;
}
}
for (int i = 25; i >= 0; i--) {
if (cnt[i] > 0) {
ans.append((char)('a' + i));
cnt[i]--;
}
}
}
return ans.toString();
}
}func sortString(s string) string {
cnt := make([]int, 26)
for i := 0; i < len(s); i++ {
cnt[s[i]-'a']++
}
ans := make([]byte, 0, len(s))
for len(ans) < len(s) {
for i := 0; i < 26; i++ {
if cnt[i] > 0 {
ans = append(ans, byte('a'+i))
cnt[i]--
}
}
for i := 25; i >= 0; i-- {
if cnt[i] > 0 {
ans = append(ans, byte('a'+i))
cnt[i]--
}
}
}
return string(ans)
}class Solution {
public:
string sortString(string s) {
vector<int> cnt(26, 0);
for (char c : s) {
cnt[c - 'a']++;
}
string ans;
ans.reserve(s.size());
while (ans.size() < s.size()) {
for (int i = 0; i < 26; i++) {
if (cnt[i] > 0) {
ans.push_back('a' + i);
cnt[i]--;
}
}
for (int i = 25; i >= 0; i--) {
if (cnt[i] > 0) {
ans.push_back('a' + i);
cnt[i]--;
}
}
}
return ans;
}
};class Solution:
def sortString(self, s: str) -> str:
cnt = [0] * 26
for ch in s:
cnt[ord(ch) - ord('a')] += 1
ans = []
while len(ans) < len(s):
for i in range(26):
if cnt[i] > 0:
ans.append(chr(ord('a') + i))
cnt[i] -= 1
for i in range(25, -1, -1):
if cnt[i] > 0:
ans.append(chr(ord('a') + i))
cnt[i] -= 1
return "".join(ans)/**
* @param {string} s
* @return {string}
*/
var sortString = function(s) {
const cnt = new Array(26).fill(0);
for (const ch of s) {
cnt[ch.charCodeAt(0) - 97]++;
}
const ans = [];
while (ans.length < s.length) {
for (let i = 0; i < 26; i++) {
if (cnt[i] > 0) {
ans.push(String.fromCharCode(97 + i));
cnt[i]--;
}
}
for (let i = 25; i >= 0; i--) {
if (cnt[i] > 0) {
ans.push(String.fromCharCode(97 + i));
cnt[i]--;
}
}
}
return ans.join("");
};中文
题目概述
给定字符串 s，按照题意反复执行两段操作：先按从小到大各取一个可用字符，再按从大到小各取一个可用字符，直到字符全部取完，返回构造后的字符串。
核心思路
字符范围固定为 26 个小写字母。先做频次数组统计，然后严格按 a→z 与 z→a 交替扫描，每次每个字母最多取 1 个，就能直接模拟题目规则。
算法步骤
- 用 cnt[26] 统计每个字母出现次数。
- 当答案长度还没达到 s.length() 时：
1）顺序扫描 0..25，若 cnt[i] > 0，追加并减一。
2）逆序扫描 25..0，同样处理。
- 最终返回拼接字符串。
复杂度分析
设字符串长度为 n。
时间复杂度：整体为 O(n)。
空间复杂度：O(26)，即 O(1)。
常见陷阱
- 漏掉“升序一轮 + 降序一轮”的交替结构。
- 一轮里把同一字母连续取多个，违反“每轮每字母最多取一个”的规则。
- 用排序后反复删除字符，逻辑复杂且性能不稳定。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public String sortString(String s) {
int[] cnt = new int[26];
for (char c : s.toCharArray()) {
cnt[c - 'a']++;
}
StringBuilder ans = new StringBuilder();
while (ans.length() < s.length()) {
for (int i = 0; i < 26; i++) {
if (cnt[i] > 0) {
ans.append((char)('a' + i));
cnt[i]--;
}
}
for (int i = 25; i >= 0; i--) {
if (cnt[i] > 0) {
ans.append((char)('a' + i));
cnt[i]--;
}
}
}
return ans.toString();
}
}func sortString(s string) string {
cnt := make([]int, 26)
for i := 0; i < len(s); i++ {
cnt[s[i]-'a']++
}
ans := make([]byte, 0, len(s))
for len(ans) < len(s) {
for i := 0; i < 26; i++ {
if cnt[i] > 0 {
ans = append(ans, byte('a'+i))
cnt[i]--
}
}
for i := 25; i >= 0; i-- {
if cnt[i] > 0 {
ans = append(ans, byte('a'+i))
cnt[i]--
}
}
}
return string(ans)
}class Solution {
public:
string sortString(string s) {
vector<int> cnt(26, 0);
for (char c : s) {
cnt[c - 'a']++;
}
string ans;
ans.reserve(s.size());
while (ans.size() < s.size()) {
for (int i = 0; i < 26; i++) {
if (cnt[i] > 0) {
ans.push_back('a' + i);
cnt[i]--;
}
}
for (int i = 25; i >= 0; i--) {
if (cnt[i] > 0) {
ans.push_back('a' + i);
cnt[i]--;
}
}
}
return ans;
}
};class Solution:
def sortString(self, s: str) -> str:
cnt = [0] * 26
for ch in s:
cnt[ord(ch) - ord('a')] += 1
ans = []
while len(ans) < len(s):
for i in range(26):
if cnt[i] > 0:
ans.append(chr(ord('a') + i))
cnt[i] -= 1
for i in range(25, -1, -1):
if cnt[i] > 0:
ans.append(chr(ord('a') + i))
cnt[i] -= 1
return "".join(ans)/**
* @param {string} s
* @return {string}
*/
var sortString = function(s) {
const cnt = new Array(26).fill(0);
for (const ch of s) {
cnt[ch.charCodeAt(0) - 97]++;
}
const ans = [];
while (ans.length < s.length) {
for (let i = 0; i < 26; i++) {
if (cnt[i] > 0) {
ans.push(String.fromCharCode(97 + i));
cnt[i]--;
}
}
for (let i = 25; i >= 0; i--) {
if (cnt[i] > 0) {
ans.push(String.fromCharCode(97 + i));
cnt[i]--;
}
}
}
return ans.join("");
};
Comments