اسٹرنگ لیٹ کوڈ حل میں کمی بڑھتی جارہی ہے


مشکل سطح آرام سے
اکثر پوچھا جاتا ہے اکونا دارالحکومت
چھانٹ سلک

اسٹرنگ لیٹ کوڈ حل میں اضافہ بڑھتا ہوا مسئلہ بیان کرتا ہے کہ ہمیں ایک سٹرنگ ان پٹ کے طور پر ہمیں ان پٹ میں ترمیم کرنے کی ضرورت ہے۔ یا جیسا کہ سوال کا بیان ہے ، ہمیں اسے ترتیب دینے کی ضرورت ہے۔ یہاں ترتیب دینے والی اصطلاح کا لازمی مطلب یہ نہیں ہے کہ صرف حرف ترتیب دیں۔ ہم خطوں کو سختی سے بڑھتے ہوئے ترتیب میں ترتیب دینے کے پہلے مخصوص ترتیب میں ترتیب دیں گے جب تک کہ ہم بڑھتے ہوئے کردار تک نہ پہنچ جائیں۔ اور جیسے ہی ہم سب سے بڑے کردار تک پہنچتے ہیں ، ہم خطوط کو سختی سے کم ترتیب میں ترتیب دینا شروع کرتے ہیں جس سے شروع ہونے والے سب سے بڑے کردار سے شروع ہوتا ہے۔ ہمیں اس عمل کو اس وقت تک دہرانے کی ضرورت ہے جب تک کہ سٹرنگ کے پورے حروف استعمال نہ ہوں۔ تو ہمیشہ کی طرح ، آئیے پہلے کچھ مثالوں کی جانچ پڑتال کریں۔

اسٹرنگ لیٹ کوڈ حل میں کمی بڑھتی جارہی ہے

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

پیچیدگی کا تجزیہ

وقت کی پیچیدگی

O (N) ، چونکہ الگورتھم میں بیرونی لوپ ، اس وقت تک چلتا ہے جب تک تعدد صف میں حروف باقی نہ رہ جائیں۔

خلائی پیچیدگی

O (N) ، کیونکہ نئی سٹرنگ اتنی ہی جگہ لے جاتی ہے جتنی ان پٹ نے لی ہے۔