Date: 2026-06-06
Time: 17:03
This file solves LeetCode 1370: Increasing Decreasing String. It implements the "sort string" algorithm that repeatedly sweeps through available characters in ascending then descending order, appending one of each to the result until all characters are consumed. The file is self-contained: solution class + unit tests in one module.
Solution.sortString(s: str) -> strThe core algorithm. Takes a string of lowercase English letters and returns a reordered string built by alternating forward (a→z) and backward (z→a) sweeps through the character set.
Contract: Input must be lowercase English letters only. Output is a permutation of the input with the same character frequencies.
TestSortStringNine test cases covering: LeetCode examples, single character, uniform characters, pre-sorted/reverse-sorted inputs, and a full-alphabet input.
Counting sort via fixed-size array: Rather than using collections.Counter or sorting the string, the solution uses a 26-element integer array (count) indexed by character ordinal offset. This is the canonical approach when the alphabet is small and known — O(1) space (fixed 26), avoids hash overhead.
Drain loop with remaining counter: The remaining variable tracks total characters left. The outer while remaining > 0 loop runs until all characters are consumed. Each inner loop (forward sweep, backward sweep) decrements both the per-character count and the global remaining counter, so the loop terminates in at most ceil(len(s) / numdistinctchars) iterations of the outer loop.
Append-to-list then join: Standard Python idiom for string building — result is a list, joined at the end. Avoids O(n²) string concatenation.
Imports: Only unittest from the standard library. No external dependencies.
Imported by: The "Imported By" list in the prompt is misleading — those are test files from *other* problems that import unittest, not files that import this module. This solution is standalone.
1. Build a frequency array count[0..25] by scanning input string once — O(n).
2. Enter drain loop:
count[i] > 0, append it and decrement.3. Repeat until remaining == 0.
4. Join the result list into a string and return.
Each full iteration of the outer loop appends at most one instance of each distinct character (once forward, once backward). For input "aaaabbbbcccc", the first iteration appends a,b,c (forward) then c,b,a (backward) = "abccba", then repeats for the second batch.
sum(count) == remaining at all times — these are kept in sync by decrementing both together.remaining.None. The function assumes valid input (lowercase English letters). No bounds checking, no type validation. Invalid input (uppercase, non-alpha, empty string) would silently produce incorrect results or an empty string — but LeetCode constraints guarantee valid input.
increasing-decreasing-string/test_solution.py — Separate test file that may contain additional edge cases beyond the inline testsfind-common-characters/solution.py:commonChars — Another problem using the 26-element counting array pattern for character frequency manipulationcounting-sort-in-leetcode — Many easy string problems in this repo likely share the fixed-size frequency array idiom; compare approaches across solutionsincreasing-decreasing-string/review.md — Code review notes that may highlight alternative approaches or complexity analysissort-string-linear-time — sortString runs in O(n * 26) = O(n) time where n is the input length, since each character is appended exactly once across all sweep iterationssort-string-constant-space — The count array is always exactly 26 elements regardless of input size; auxiliary space is O(1) beyond the outputsweep-ordering-guarantee — Characters within each forward sweep are in strictly ascending order and within each backward sweep in strictly descending order, by construction of the index iterationremaining-invariant — The remaining counter equals sum(count) at every point in execution, ensuring the drain loop terminates exactly when all characters are consumed