రెండు తీగలను అనగ్రామ్ లీట్‌కోడ్ సొల్యూషన్స్ చేయడానికి కనీస సంఖ్య దశలు


కఠినత స్థాయి సులువు
తరచుగా అడుగుతుంది అమెజాన్ బ్లూమ్బెర్గ్ సిట్రిక్స్ మైక్రోసాఫ్ట్ <span style="font-family: Mandali; ">ట్విట్టర్</span>
స్ట్రింగ్

సమస్యల నివేదిక

ఈ సమస్యలో, మాకు రెండు ఇవ్వబడ్డాయి తీగలను లోయర్-కేస్ ఇంగ్లీష్ అక్షరాలను కలిగి ఉన్న 's' & 't'. ఒక ఆపరేషన్‌లో, మనం 't' స్ట్రింగ్‌లోని ఏదైనా అక్షరాన్ని ఎన్నుకోవచ్చు మరియు దానిని వేరే అక్షరానికి మార్చవచ్చు. 'T' ను చేయడానికి మేము అలాంటి ఆపరేషన్ల యొక్క కనీస సంఖ్యను కనుగొనాలి విపర్యయసిద్ధంను యొక్క 's'.

ఉదాహరణ

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

రెండు తీగలను అనగ్రామ్ చేయడానికి కనీస సంఖ్య దశలు

అప్రోచ్

రెండు తీగలలో ఒకేలా ఉండే అక్షరాలకు ఎటువంటి ఆపరేషన్లు అవసరం లేదని స్పష్టమైంది (మనకు వాటి ఏకకాల ఉనికి అవసరం, ఒకే క్రమం కాదు). ముఖ్యమైన భాగం ఏమిటంటే, మిగిలిన చార్టర్లకు మనం ఎలా పరిష్కరించగలమో అర్థం చేసుకోవడం.

స్ట్రింగ్ 't' లోని కొన్ని అక్షరాలతో సరిపోయే స్ట్రింగ్ 's' లోని అన్ని అక్షరాలను మేము మొదట క్లియర్ చేసాము, ఆపై 't' స్ట్రింగ్‌లోని సంబంధిత అక్షరాలను తొలగించాము. ఉదాహరణ s = “గిన్ని”, t = “హ్యారీ”. రెండు తీగలలోని సరిపోలే అక్షరాలను తీసివేసిన తరువాత, s = “జిన్”, t = “harr”. ఇప్పుడు, 't' స్ట్రింగ్‌లోని ప్రతి అక్షరం స్పష్టంగా ఉంది తప్పక కొన్ని ఇతర పాత్రలకు మార్చబడుతుంది, తద్వారా 's' అక్షరాలు కూడా ఇందులో ఉంటాయి.

మేము ఇప్పటికే 's' మరియు 't' లోని అన్ని జతల సరిపోలికలను తొలగించామని గుర్తుంచుకోండి. కాబట్టి, '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. = స్ట్రింగ్ 's' & 't' యొక్క పొడవు.

అంతరిక్ష సంక్లిష్టత 

O (1), రెండు తీగలలో పరిమిత సంఖ్యలో ప్రత్యేకమైన అక్షరాలు ఉన్నందున, మెమరీ స్థలం స్థిరంగా ఉంటుందని మాకు తెలుసు.