दो स्ट्रिंग्स एनाग्राम लेटकोड सॉल्यूशंस बनाने के लिए न्यूनतम चरणों की संख्या


कठिनाई स्तर आसान
में अक्सर पूछा वीरांगना ब्लूमबर्ग Citrix माइक्रोसॉफ्ट Twitter
तार

समस्या का विवरण

इस समस्या में, हमें दो दिए गए हैं तार 's' & 't' जिसमें लोअर-केस अंग्रेजी अक्षर होते हैं। एक ऑपरेशन में, हम किसी भी वर्ण को 't' में चुन सकते हैं और इसे किसी अन्य वर्ण में बदल सकते हैं। हमें 't' a बनाने के लिए ऐसे ऑपरेशनों की न्यूनतम संख्या खोजने की आवश्यकता है वर्ण - विपर्यय 's' का।

उदाहरण

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

दो स्ट्रिंग्स एनाग्राम बनाने के लिए न्यूनतम चरणों की संख्या

दृष्टिकोण

यह स्पष्ट है कि दोनों तारों में समान वर्णों को किसी भी संचालन की आवश्यकता नहीं है (जैसा कि हमें उनकी एक साथ उपस्थिति की आवश्यकता है, समान आदेश नहीं)। महत्वपूर्ण हिस्सा यह समझना है कि हम बाकी चार्जर्स के लिए कैसे हल कर सकते हैं।

मान लें कि हमने पहले स्ट्रिंग 's' में सभी वर्णों को साफ़ किया, जो स्ट्रिंग 't' के किसी वर्ण से मेल खाते हैं, और फिर स्ट्रिंग 't' में उन संबंधित वर्णों को हटा दिया। उदाहरण s = "ginny", t = "harry"। दोनों तारों में मिलान वर्णों को हटाने के बाद, s = "ginn", t = "harr"। अब, यह स्पष्ट है कि स्ट्रिंग 'टी' में हर चरित्र चाहिए किसी अन्य चरित्र में बदला जाए ताकि 's' के पात्र भी उसमें मौजूद हों।

याद रखें कि हमने 's' और 't' में मिलान के सभी जोड़े पहले ही हटा दिए थे। तो, 't' में कोई भी वर्ण नहीं होगा जो 's' में मौजूद है। इसे हैश टेबल की मदद से आसानी से लागू किया जा सकता है।

दो स्ट्रिंग्स एनाग्रम Leetcode समाधान बनाने के लिए चरणों की न्यूनतम संख्या का कार्यान्वयन

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

जावा प्रोग्राम

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

दो स्ट्रिंग्स एनाग्रम Leetcode समाधान बनाने के लिए न्यूनतम चरणों की जटिलता का विश्लेषण

समय जटिलता

ओ (एन), जहां एन = स्ट्रिंग 'एस' और 'टी' की लंबाई।

अंतरिक्ष जटिलता 

O (1), चूंकि दोनों तारों में सीमित संख्या में अद्वितीय अक्षर हैं, हम जानते हैं कि मेमोरी स्पेस स्थिर रहता है।