Increasing Decreasing String

Increasing decreasing string

1. Pick the smallest character from s and append it to the result.

1. Pick the smallest character from s which is greater than the last appended character to the result and append it.

1. Repeat step 2 until you cannot pick more characters.

1. Pick the largest character from s and append it to the result.

1. Pick the largest character from s which is smaller than the last appended character to the result and append it.

1. Repeat step 5 until you cannot pick more characters.

1. Repeat the steps from 1 to 6 until you pick all characters from s.

Example:

Input: str="aaaabbbbcccc"
Output: "abccbaabccba"

Approach

Java

import java.util.HashMap;

public class IncreasingDecreasingString {
    public static void main(String[] args) {
        String str = "leetcode";
        String sort = sortString(str);
        System.out.println(sort);
    }

    private static String sortString(String s) {
        StringBuffer res = new StringBuffer();
        HashMap<Character, Integer> mapS = new HashMap<>();
        // iterate till end of s
        for (int i = 0; i < s.length(); i++) {
            // set frequency of string
            mapS.put(s.charAt(i), mapS.getOrDefault(s.charAt(i), 0) + 1);
        }
        int n = s.length();
        int i = 0;
        while (n > 0) {
            i = 0;
            // increasing string
            while (i < 26 && n > 0) {
                char c = (char) (i + 97);
                if (mapS.containsKey(c) && mapS.get(c) > 0) {
                    res.append(c);
                    n--;
                    mapS.put(c, mapS.get(c) - 1);
                }
                i++;
            }
            i = 25;

            // decreasing string
            while (i >= 0 && n > 0) {
                char c = (char) (i + 97);
                if (mapS.containsKey(c) && mapS.get(c) > 0) {
                    res.append(c);
                    n--;
                    mapS.put(c, mapS.get(c) - 1);
                }
                i--;
            }
        }
        return res.toString();

    }
}

C++

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

string sortString(string s) 
{
    string res="";
    int n=s.size();
    int f[26]={0};
    for(int i=0;i<n;i++)
        f[s[i]-'a']++;
    int i=0;
     while(n>0)
        {
            i=0;

            //increasing string
            while(i<26 &&n)
            {
                if(f[i]>0)
                {
                    res+='a'+i;
                    n--;
                    f[i]--;
                }
               i++;
            }
            i=25;

            //decreasing string
            while(i>=0&&n)
            {
                if(f[i]>0)
                {
                    res+='a'+i;
                    n--;
                    f[i]--;
                }
              i--;
            }
     }
      return res;
}
int main()
{
    string str="rat";
    cout<<sortString(str);
    return 0;
}