ינקרעאַסינג דיקריסינג סטרינג לעעטקאָדע סאַלושאַן


שוועריקייט לעוועל גרינג
אָפט געבעטן אין אַקונאַ קאַפּיטאַל
סאָרטינג שטריקל

די פּראָבלעם ינקריסינג דיקריסינג סטרינג לעעטקאָדע סאַלושאַן שטאַטן אַז מיר געבן אַ שטריקל ווי ינפּוט. מיר דאַרפֿן צו מאָדיפיצירן די אַרייַנשרייַב. אָדער ווי די קשיא זאגט, מיר דאַרפֿן צו סאָרט עס. דער טערמין סאָרט דאָ טוט נישט דאַווקע מיינען סימפּלי סאָרטינג די אותיות. מיר וועלן סאָרט די שטריקל אין אַ ספּעציפיש סדר פון ערשטער עריינדזשינג די אותיות אין שטרענג ינקריסינג סדר ביז מיר דערגרייכן די ינקריסינג כאַראַקטער. און ווען מיר דערגרייכן דעם גרעסטן כאַראַקטער, מיר אָנהייבן צו צולייגן אותיות אין שטרענג דיקריסינג סדר, סטאַרטינג מיט דעם גרעסטן כאַראַקטער בנימצא. מיר דאַרפֿן צו איבערחזרן דעם פּראָצעס ביז די אותיות פון די גאנצע שטריקל זענען געניצט. אַזוי ווי געוויינטלעך, לאָזן אונדז ערשטער טשעק עטלעכע ביישפילן.

ינקרעאַסינג דיקריסינג סטרינג לעעטקאָדע סאַלושאַן

s = "aaaabbbbcccc"
"abccbaabccba"

דערקלערונג: ווי אויבן סטייטיד, די סאָרטעד שטריקל מוזן נאָכגיין אַ זיכער מוסטער. ערשטער, די אותיות מוזן זיין אין אַ שטרענג ינקריסינג מוסטער און דערנאָך אין דיקריסינג מוסטער. דער רעזולטאַט דאָ גייט די זעלבע מוסטער. די שטריקל סטאַרץ מיט a און גייט אַ שטרענג ינקריסינג מוסטער ביז c. דערנאָך סטאַרטינג מיט c ענדס מיט a. דער פּראָצעס איז ריפּיטיד ביז די אותיות פון די ינפּוט שטריקל זענען ויסגעמאַטערט.

s = "rat"
"art"

דערקלערונג: די סאָרטעד (ריזאַלטיד) שטריקל סטאַרץ מיט דער קלענסטער כאַראַקטער און גייט דער זעלביקער מוסטער ביז מיר זענען לינקס אָן אותיות.

צוגאַנג פֿאַר ינקריסינג דיקריסינג סטרינג לעעטקאָדע לייזונג

די פּראָבלעם ינקרעאַסינג דיקריסינג סטרינג לעעטקאָדע סאַלושאַן געבעטן אונדז צו סאָרט די געגעבן אַרייַנשרייַב שטריקל אין אַ זיכער מאָדע. דער מוסטער איז דיסקרייבד אין דעטאַל אויבן. אין קורץ, צולייגן די אַרייַנשרייַב אותיות ערשטער אין שטרענג ינקריסינג סדר און דאַן אין שטרענג דיקריסינג סדר ביז קיין אותיות בלייַבן. אַזוי, מיר מאַכן אַ אָפטקייַט מענגע צו קראָם די ציילן פון יעדער כאַראַקטער אין די ינפּוט. דערנאָך מיר נאָר לויפן אַ שלייף איבער די אָפטקייַט מענגע ביז אַלע די אותיות אין עס זענען ויסגעמאַטערט.

די ויסווייניקסט שלייף לויפט ביז עס זענען אותיות (אָפטקייַט גרעסער ווי 1) אין די אָפטקייַט מענגע. ינער שלייף אַפּענדז די כאַראַקטער אין אַ צייַטווייַליק שטריקל. די צייטווייליגע שטריקל איז אַפּפּענדעד צו די ענטפער דיפּענדינג אויף די דרייען. אויב עס איז דער ערשטער קער ווען די צייטווייליגע שטריקל איז מוסיף, עס איז צוגעגעבן אין דער זעלביקער ינקריסינג שטייגער. אָבער אויב עס איז אַן גלאַט קער, די שטריקל איז ריווערסט איידער אַפּפּענדינג צו ענטפֿערן. נאָך יגזאָסטשאַן פון אותיות אין די אָפטקייַט מענגע. די אַלגערידאַם קערט אַ נייַע ענטפער שטריקל צו די פאַך פונקציע.

קאָדעקס

C ++ קאָוד פֿאַר ינקרעאַסינג דיקריסינג סטרינג לעעטקאָדע סאַלושאַן

#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

דזשאַוואַ קאָוד פֿאַר ינקרעאַסינג דיקריסט סטרינג לעעטקאָדע סאַלושאַן

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

קאַמפּלעקסיטי אַנאַליסיס

צייט קאַמפּלעקסיטי

אָ (N), זינט די ויסווייניקסט שלייף אין די אַלגערידאַם לויפט ביז די אותיות זענען לינקס אין די אָפטקייַט מענגע.

ספעיס קאַמפּלעקסיטי

אָ (N), ווייַל די נייַע שטריקל נעמט די זעלבע פּלאַץ ווי די ינפּוט איז גענומען.