Increasing Decreasing String - Practice Coding Problems

Increasing Decreasing String - Problem

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.

Input & Output

Example 1 — Basic Case

$ Input: s = "aaaabbbbcccc"

› Output: "abccbaabccba"

💡 Note: First cycle: ascending a→b→c, descending c→b→a. Second cycle: ascending a→b→c, descending c→b→a. Result: abccbaabccba

Example 2 — Single Character

$ Input: s = "rat"

› Output: "art"

💡 Note: Ascending phase picks 'a', then 'r', then 't'. No characters left for descending phase. Result: art

Example 3 — Repeated Pattern

$ Input: s = "leetcode"

› Output: "cdelotee"

💡 Note: First ascending: c→d→e→l→o→t. Then descending: e→e. All characters used. Result: cdelotee

Constraints

1 ≤ s.length ≤ 500
s consists of lowercase English letters only

Visualization

Tap to expand

Understanding the Visualization

Input

String 'aaaabbbbcccc' with character frequencies

Process

Alternate ascending (a→b→c) and descending (c→b→a) selections

Output

Final string 'abccbaabccba' following the pattern

Key Takeaway

🎯 Key Insight: Use frequency counting to avoid string manipulation and systematically alternate between ascending and descending character selection

Asked in

a Amazon 15 G Google 12 M Microsoft 8

The key insight is to count character frequencies first, then alternate between ascending and descending phases efficiently. Best approach uses frequency counter with O(n × k) time where k=26 for lowercase letters, effectively O(n). Space: O(k) = O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force with String Scanning	O(n²)	O(n)	Repeatedly scan the remaining string to find next character according to rules
Frequency Counter Approach	O(n × k)	O(k)	Count character frequencies first, then systematically pick characters

Brute Force with String Scanning — Algorithm Steps

Convert string to list for easy removal
Alternate between ascending and descending phases
In each phase, scan remaining characters to find next valid one
Remove found character and append to result

Visualization

Tap to expand

Step-by-Step Walkthrough

Initial String

Start with input string 'aaaabbbbcccc'

Sort & Pick

Sort remaining chars, pick smallest for ascending phase

Result Built

Continue until all characters processed

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int compare_asc(const void *a, const void *b) {
    return *(char*)a - *(char*)b;
}

int compare_desc(const void *a, const void *b) {
    return *(char*)b - *(char*)a;
}

char* solution(char* s) {
    int len = strlen(s);
    char* chars = (char*)malloc((len + 1) * sizeof(char));
    strcpy(chars, s);
    
    char* result = (char*)malloc((len + 1) * sizeof(char));
    int result_idx = 0;
    int chars_len = len;
    
    while (chars_len > 0) {
        // Ascending phase
        qsort(chars, chars_len, sizeof(char), compare_asc);
        result[result_idx++] = chars[0];
        memmove(chars, chars + 1, (chars_len - 1) * sizeof(char));
        chars_len--;
        
        // Continue ascending
        int i = 0;
        while (i < chars_len) {
            if (chars[i] > result[result_idx - 1]) {
                result[result_idx++] = chars[i];
                memmove(chars + i, chars + i + 1, (chars_len - i - 1) * sizeof(char));
                chars_len--;
            } else {
                i++;
            }
        }
        
        if (chars_len == 0) break;
        
        // Descending phase
        qsort(chars, chars_len, sizeof(char), compare_desc);
        result[result_idx++] = chars[0];
        memmove(chars, chars + 1, (chars_len - 1) * sizeof(char));
        chars_len--;
        
        // Continue descending
        i = 0;
        while (i < chars_len) {
            if (chars[i] < result[result_idx - 1]) {
                result[result_idx++] = chars[i];
                memmove(chars + i, chars + i + 1, (chars_len - i - 1) * sizeof(char));
                chars_len--;
            } else {
                i++;
            }
        }
    }
    
    result[result_idx] = '\0';
    free(chars);
    return result;
}

int main() {
    char s[1001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    char* result = solution(s);
    printf("%s\n", result);
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

For each of n characters, we scan the remaining string which averages n/2 characters

⚠ Quadratic Growth

Space Complexity

O(n)

Converting string to list for manipulation requires O(n) extra space

⚡ Linearithmic Space

28.4K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force with String Scanning — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler