બે સ્ટ્રિંગ્સ એનાગ્રામ લીટકોડ સોલ્યુશન્સ બનાવવા માટેના ઓછામાં ઓછા પગલાઓની સંખ્યા


મુશ્કેલી સ્તર સરળ
વારંવાર પૂછવામાં આવે છે એમેઝોન બ્લૂમબર્ગ સિટ્રીક્સ માઈક્રોસોફ્ટ Twitter
શબ્દમાળા

સમસ્યા નિવેદન

આ સમસ્યામાં, અમને બે આપવામાં આવે છે શબ્દમાળાઓ લોઅર-કેસ અંગ્રેજી અક્ષરોવાળી 'ઓ' અને 'ટી'. એક operationપરેશનમાં, આપણે શબ્દમાળા 't' માં કોઈપણ પાત્રને પસંદ કરી શકીએ છીએ અને તેને કોઈ બીજા પાત્રમાં બદલી શકીએ છીએ. 'ટી' ને બનાવવા માટે આપણે આ પ્રકારની કામગીરીની લઘુત્તમ સંખ્યા શોધવાની જરૂર છે એનાગ્રામ ની 's'.

ઉદાહરણ

s = "bab", t = "aba"
1
s = "leetcode", t = "practice"
5

બે સ્ટ્રિંગ્સ એનાગ્રામ બનાવવા માટેના ઓછામાં ઓછા પગલાઓની સંખ્યા

અભિગમ

તે સ્પષ્ટ છે કે બંને તારમાં સમાન અક્ષરોને કોઈ કામગીરીની જરૂર હોતી નથી (કારણ કે અમને તેમની એક સાથે હાજરીની જરૂર છે, સમાન ક્રમમાં નહીં). મહત્વપૂર્ણ ભાગ એ સમજવાનો છે કે આપણે બાકીના ચાર્ટટર્સ માટે કેવી રીતે હલ કરી શકીએ.

જણાવી દઈએ કે આપણે પહેલા શબ્દમાળા 't' માંના બધા અક્ષરોને સાફ કર્યા હતા, જે શબ્દમાળા 't' ના કેટલાક પાત્ર સાથે મેળ ખાય છે, અને ત્યારબાદ 't' શબ્દમાળામાં લાગતાવળગતા અક્ષરોને કા deletedી નાખ્યાં છે. ઉદાહરણ s = “જીની”, ટી = “હેરી”. બંને શબ્દમાળાઓ, s = "ginn", t = "harr" માં બંધબેસતા અક્ષરોને દૂર કર્યા પછી. હવે, તે સ્પષ્ટ છે કે શબ્દમાળા 't' માં દરેક પાત્ર અને શોધવાતે એસડબલ્યુ ફાઇલોની બીજા કોઈ પાત્રમાં બદલાઇ જાઓ જેથી તેમાં 's' ના પાત્રો પણ હાજર હોય.

યાદ રાખો કે અમે પહેલાથી જ 's' અને 't' માં મેચિંગ્સની બધી જોડીઓ દૂર કરી દીધી છે. તેથી, 't' માં કોઈ પાત્ર હશે નહીં જે 's' માં હાજર છે. હેશ ટેબલની સહાયથી આને સરળતાથી અમલમાં મૂકી શકાય છે.

બે સ્ટ્રિંગ્સ એનાગ્રામ લીટકોડ સોલ્યુશન્સ બનાવવા માટે ઓછામાં ઓછી સંખ્યાના પગલાઓની અમલીકરણ

સી ++ પ્રોગ્રામ

#include <bits/stdc++.h>

using namespace std;

int minSteps(string s, string t) {
    unordered_map <int , int> f;
    int ans = 0;
    for(char &c : s) {
        f[c - 'a']++;
    }

    for(char &c : t) {
        f[c - 'a']--;
    }

    for(auto &c : f) {
        if(c.second != 0)
            ans++;
    }

    return ans / 2;
}

int main() {
    string s = "bab" , t = "aba";
    cout << minSteps(s , t) << endl;
    return 0;
}

જાવા પ્રોગ્રામ

import java.util.*;
import java.io.*;
import java.util.Hashtable;
import java.util.Set;
import java.util.Iterator;

class anagrams {
    public static void main(String args[]) {
        String s = "bab" , t = "aba";
        System.out.println(minSteps(s , t));
    }

    public static int minSteps(String s , String t) {

        Hashtable <Character , Integer> f = new Hashtable<>();
        int ans = 0;
        for(char c : s.toCharArray()) {
            f.put(c , f.getOrDefault(c , 0) + 1);
        }

        for(char c : t.toCharArray()) {
            f.put(c , f.getOrDefault(c , 0) - 1);
        }

        for(char c = 'a' ; c <= 'z' ; c++) {
            if(f.containsKey(c) && f.get(c) != 0) {
                ans += Math.abs(f.get(c));
            }
        }

        return ans / 2;
    }
}
1

બે સ્ટ્રિંગ્સ એનાગ્રામ લીટકોડ સોલ્યુશન્સ બનાવવા માટે લઘુતમ સંખ્યાના પગલાઓની જટિલતા વિશ્લેષણ

સમય જટિલતા

ઓ (એન), જ્યાં એન શબ્દમાળા 's' અને 't' ની લંબાઈ.

અવકાશ જટિલતા 

ઓ (1), કેમ કે બંને તારમાં મર્યાદિત સંખ્યામાં અનન્ય અક્ષરો છે, આપણે જાણીએ છીએ કે મેમરી સ્થાન સતત રહે છે.