Increasing Decreasing String Leetcode Solution

The problem Increasing Decreasing String Leetcode Solution states that we are given a string as input. We need to modify the input. Or as the question states, we need to sort it. The term sort here does not necessarily mean simply sorting the characters. We will sort the string in a specific order of first arranging the letters in strictly increasing order until we reach the increasing character. And as we reach the largest character, we start to arrange letters in strictly decreasing order starting with the largest character available. We need to repeat this process until the entire string’s characters have been used. So as usual, let’s first check a few examples.

s = "aaaabbbbcccc"

"abccbaabccba"

Explanation: As stated above the sorted string must follow a certain pattern. First, the characters must be in a strictly increasing pattern and then in decreasing pattern. The output here follows the same pattern. The string starts with a and follows a strictly increasing pattern until c. Then again starting with c ends with a. The process is repeated until the letters of the input string are exhausted.

s = "rat"

"art"

Explanation: The sorted (resultant) string starts with the smallest character and follows the same pattern until we are left with no characters.

Approach for Increasing Decreasing String Leetcode Solution

The problem Increasing Decreasing String Leetcode Solution asked us to sort the given input string in a certain fashion. The pattern is described in detail above. In brief, arrange the input characters first in strictly increasing order and then in strictly decreasing order until no characters remain. So, we create a frequency array to store the count of each character in the input. Then we simply run a loop over the frequency array until all the characters in it are exhausted.

The outer loop runs until there are characters (frequency greater than 1) in the frequency array. Inner loop appends the character in a temporary string. This temporary string is appended to the answer depending on the turn. If it is the first turn when the temporary string is being added, it is added in the same increasing manner. But if it is an even turn, then the string is reversed before appending to answer. After the exhaustion of characters in the frequency array. The algorithm returns a new answer string to the caller function.

Code

C++ Code for Increasing Decreasing String Leetcode Solution

#include <bits/stdc++.h>
using namespace std;

string sortString(string s) {
    vector<int> frq(26, 0);
    for(auto x: s)
        frq[x-'a']++;
    int par = false;
    string ans = "";
    bool can = false;
    do{
        can = false;
        string ss = "";
        for(int i=0;i<26;i++)
            if(frq[i]){
                ss += (char)(i+'a');
                frq[i]--;
                can |= (frq[i] > 0);
            }
        if(par == true)
            reverse(ss.begin(), ss.end());
        par ^= 1;
        ans += ss;
    } while(can);
    return ans;
}

int main()
{
    cout<<sortString("aaaabbbbcccc");
}

abccbaabccba

Java Code for Increasing Decreasing String Leetcode Solution

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
  public static String sortString(String s) {
        ArrayList<Integer> frq = new ArrayList<Integer>();
        for(int i=0;i<26;i++)
            frq.add(0);
        for(int i=0;i<s.length();i++)
            frq.set(s.charAt(i)-'a', frq.get(s.charAt(i)-'a')+1);
        int par = 0;
        StringBuilder ans = new StringBuilder();
        boolean can = false;
        do{
            can = false;
            StringBuilder ss = new StringBuilder();
            for(int i=0;i<26;i++)
                if(frq.get(i)>0){
                    ss.append((char)(i+'a'));
                    frq.set(i, frq.get(i)-1);
                    can |= (frq.get(i) > 0);
                }
            if(par == 1)
                ss.reverse();
            par ^= 1;
            ans.append(ss);
        } while(can == true);
        return ans.toString();
    }
    
  public static void main (String[] args) throws java.lang.Exception
  {
    System.out.print(sortString("aaaabbbbcccc"));
  }
}

abccbaabccba

Complexity Analysis

Time Complexity

O(N), since the outer loop in the algorithm, runs until the characters are left in the frequency array.

Space Complexity

O(N), because the new string takes the same amount of space as taken by the input.