1370. Increasing Decreasing String
Model: qwen2.5-coder:14b
Topics: String,Sort
FAANG asked: 0
Acceptance rate: 77.5%
Problem Breakdown
The problem requires reordering a given string s using a specific algorithm. The goal is to construct a new string by repeatedly picking characters in increasing order, then decreasing order, and repeating this process until all characters are used.
Inputs:
- A single string
scontaining only lowercase English letters.
Outputs:
- A reordered string following the specified algorithm.
Implicit Constraints or Tricky Edge Cases:
- The string can contain duplicate characters.
- The string length is between 1 and 500 characters.
- The string consists of lowercase English letters only, so no need to handle other character types.
Intuition
A brute-force approach would involve sorting the string repeatedly and picking characters in a specific order. However, this would be inefficient due to repeated sorting operations (O(n log n) complexity).
The key insight is to use a frequency counter to keep track of how many times each character appears in the string. This allows us to efficiently pick characters in increasing and decreasing order without needing to sort the string repeatedly.
Approach
- Frequency Counter: Use an array to count the occurrences of each character in the string.
- Character Order: Maintain a list of all unique characters sorted in ascending order.
- Construct Result:
- While there are characters left to pick:
- Traverse the list of characters from smallest to largest, appending characters to the result if they still have remaining occurrences.
- Traverse the list of characters from largest to smallest, appending characters to the result if they still have remaining occurrences.
- While there are characters left to pick:
- Repeat: Continue the process until all characters are used.
Complexity Analysis
- Time Complexity: O(n), where n is the length of the string. We traverse the string a constant number of times (twice per character).
- Space Complexity: O(1) for the frequency counter, as it will have at most 26 entries (one for each lowercase English letter).
Solution
def sortString(s: str) -> str:
# Step 1: Create a frequency counter for each character in the string
freq = [0] * 26
for char in s:
freq[ord(char) - ord('a')] += 1
# Step 2: Prepare a list of characters sorted in ascending order
chars = [chr(i + ord('a')) for i in range(26)]
result = []
# Step 3: Construct the result string
while len(result) < len(s):
# Traverse from smallest to largest
for char in chars:
if freq[ord(char) - ord('a')] > 0:
result.append(char)
freq[ord(char) - ord('a')] -= 1
# Traverse from largest to smallest
for char in reversed(chars):
if freq[ord(char) - ord('a')] > 0:
result.append(char)
freq[ord(char) - ord('a')] -= 1
return ''.join(result)
Edge Cases Handled
- All Characters Same: If all characters are the same, the output will be the same as the input.
- Single Character String: The output will be the same as the input.
- Empty String: Although not explicitly mentioned in constraints, if the string is empty, the function will return an empty string.