מינימום נומער פון סטעפּס צו מאַכן צוויי סטרינגס אַנאַגראַם לעעטקאָדע סאַלושאַנז


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

פּראָבלעם סטאַטעמענט

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

בייַשפּיל

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

מינימום נומער פון סטעפּס צו מאַכן אַנאַגראַם פֿאַר צוויי סטרינגס

צוגאַנג

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

לאָמיר זאָגן מיר ערשטער קלירד אַלע די אותיות אין שטריקל 's' וואָס גלייַכן צו עטלעכע אותיות אין שטריקל 'ה' און דאַן אויסגעמעקט די קאָראַספּאַנדינג אותיות אין די שטריקל 'ה'. בייַשפּיל s = “ginny”, t = “harry”. נאָך רימוווינג די ריכטן אותיות אין ביידע סטרינגס, s = “ginn”, t = “harr”. איצט עס איז קלאָר ווי דער טאָג אַז יעדער כאַראַקטער אין שטריקל 'ה' מוזן זיין טשיינדזשד צו עטלעכע אנדערע אותיות אַזוי אַז די אותיות פון 's' זענען אויך פאָרשטעלן אין עס.

געדענקט אַז מיר האָבן שוין אַוועקגענומען אַלע פּאָר פון מאַטטשינגז אין 's' און 'ה'. אַזוי, עס וועט זיין קיין כאַראַקטער אין 'ה' וואָס איז פאָרשטעלן אין 's'. דעם קענען זיין ימפּלאַמענאַד מיט די הילף פון אַ האַש טיש.

ימפּלאַמענטיישאַן פון מינימום נומער פון סטעפּס צו מאַכן צוויי סטרינגס אַנאַגראַם לעעטקאָדע סאַלושאַנז

C ++ פּראָגראַם

#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;
}

Java פּראָגראַם

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

קאַמפּלעקסיטי אַנאַליסיס פון מינימום נומער פון סטעפּס צו מאַכן צוויי סטרינגס אַנאַגראַם לעעטקאָדע סאַלושאַנז

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

אָ (N), ווו N. = לענגקטס פון שטריקל 's' & 'ה'.

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

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