രണ്ട് സ്ട്രിംഗുകൾ നിർമ്മിക്കാനുള്ള ഏറ്റവും കുറഞ്ഞ ഘട്ടങ്ങളുടെ എണ്ണം അനഗ്രാം ലീറ്റ്കോഡ് പരിഹാരങ്ങൾ


വൈഷമ്യ നില എളുപ്പമായ
പതിവായി ചോദിക്കുന്നു ആമസോൺ ബ്ലൂംബർഗ് ക്സെൻ മൈക്രോസോഫ്റ്റ് ട്വിറ്റർ
സ്ട്രിംഗ്

പ്രശ്നം പ്രസ്താവന

ഈ പ്രശ്‌നത്തിൽ, ഞങ്ങൾക്ക് രണ്ട് നൽകിയിരിക്കുന്നു സ്ട്രിംഗുകൾ ചെറിയ അക്ഷരങ്ങളുള്ള ഇംഗ്ലീഷ് പ്രതീകങ്ങൾ അടങ്ങിയ 's' & 't'. ഒരു പ്രവർത്തനത്തിൽ, നമുക്ക് 't' സ്ട്രിംഗിലെ ഏത് പ്രതീകവും തിരഞ്ഞെടുത്ത് മറ്റേതെങ്കിലും പ്രതീകത്തിലേക്ക് മാറ്റാം. 'ടി' ആക്കുന്നതിന് അത്തരം പ്രവർത്തനങ്ങളുടെ ഏറ്റവും കുറഞ്ഞ എണ്ണം ഞങ്ങൾ കണ്ടെത്തേണ്ടതുണ്ട് അനഗ്രാം ന്റെ 'ന്റെ'.

ഉദാഹരണം

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

രണ്ട് സ്ട്രിംഗുകൾ അനഗ്രാം നിർമ്മിക്കുന്നതിനുള്ള ഏറ്റവും കുറഞ്ഞ ഘട്ടങ്ങൾ

സമീപനം

രണ്ട് സ്ട്രിംഗുകളിലും ഒരേപോലെയുള്ള പ്രതീകങ്ങൾക്ക് പ്രവർത്തനങ്ങളൊന്നും ആവശ്യമില്ലെന്ന് വ്യക്തമാണ് (ഞങ്ങൾക്ക് ഒരേസമയം സാന്നിദ്ധ്യം ആവശ്യമാണ്, ഒരേ ക്രമമല്ല). ബാക്കി ചാർ‌ട്ടറുകൾ‌ക്കായി എങ്ങനെ പരിഹരിക്കാമെന്ന് മനസിലാക്കുക എന്നതാണ് പ്രധാന ഭാഗം.

'ടി' എന്ന സ്‌ട്രിംഗിലെ ചില പ്രതീകങ്ങളുമായി പൊരുത്തപ്പെടുന്ന സ്‌ട്രിംഗിലെ എല്ലാ പ്രതീകങ്ങളും ഞങ്ങൾ ആദ്യം മായ്ച്ചുകളഞ്ഞു, തുടർന്ന് 'ടി' സ്‌ട്രിംഗിലെ അനുബന്ധ പ്രതീകങ്ങൾ ഇല്ലാതാക്കി. ഉദാഹരണം s = “ജിന്നി”, ടി = “ഹാരി”. രണ്ട് സ്ട്രിംഗുകളിലും പൊരുത്തപ്പെടുന്ന പ്രതീകങ്ങൾ നീക്കം ചെയ്ത ശേഷം, s = “ജിൻ”, ടി = “ഹാർ”. ഇപ്പോൾ, 't' സ്ട്രിംഗിലെ ഓരോ പ്രതീകവും വ്യക്തമാണ് ആവശമാകുന്നു മറ്റേതെങ്കിലും പ്രതീകത്തിലേക്ക് മാറ്റുന്നതിലൂടെ 's' ന്റെ പ്രതീകങ്ങളും അതിൽ ഉണ്ടാകും.

'S', 't' എന്നിവയിലെ എല്ലാ ജോഡി പൊരുത്തപ്പെടുത്തലുകളും ഞങ്ങൾ ഇതിനകം നീക്കംചെയ്തുവെന്നോർക്കുക. അതിനാൽ, 'ടി'യിൽ' എസ് 'എന്നതിൽ ഒരു പ്രതീകവും ഉണ്ടാകില്ല. ഒരു ഹാഷ് പട്ടികയുടെ സഹായത്തോടെ ഇത് എളുപ്പത്തിൽ നടപ്പിലാക്കാൻ കഴിയും.

രണ്ട് സ്ട്രിംഗുകൾ അനഗ്രാം ലീറ്റ്കോഡ് സൊല്യൂഷനുകൾ നിർമ്മിക്കുന്നതിനുള്ള ഏറ്റവും കുറഞ്ഞ ഘട്ടങ്ങൾ നടപ്പിലാക്കുക

സി ++ പ്രോഗ്രാം

#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

രണ്ട് സ്ട്രിംഗുകൾ നിർമ്മിക്കുന്നതിനുള്ള ഏറ്റവും കുറഞ്ഞ ഘട്ടങ്ങളുടെ സങ്കീർണ്ണത വിശകലനം അനഗ്രാം ലീറ്റ്കോഡ് പരിഹാരങ്ങൾ

സമയ സങ്കീർണ്ണത

O (N), ഇവിടെ N. = സ്ട്രിംഗിന്റെ ദൈർഘ്യം & ടി.

ബഹിരാകാശ സങ്കീർണ്ണത 

O (1), രണ്ട് സ്ട്രിംഗുകളിലും പരിമിതമായ എണ്ണം അദ്വിതീയ പ്രതീകങ്ങൾ ഉള്ളതിനാൽ, മെമ്മറി സ്പേസ് സ്ഥിരമായി നിലനിൽക്കുന്നുവെന്ന് നമുക്കറിയാം.