दो समान वर्ण लेटकोड सॉल्यूशन के बीच सबसे बड़ा पदार्थ


कठिनाई स्तर आसान
तार

दो समान वर्ण लेटकोड सॉल्यूशन के बीच सबसे बड़ी समस्या, हमें सबसे बड़ी सबस्ट्रिंग की लंबाई का पता लगाने के लिए कहती है। यहां, एक शर्त को प्रतिस्थापन पर लगाया गया है। प्रतिस्थापन एक ही वर्ण के बीच होना चाहिए। इतना स्ट्रिंग कम से कम दो समान वर्ण होने चाहिए, ताकि उत्पादन स्वाभाविक संख्या में हो -१ और वापस आ जाए। लेकिन समाधान के साथ आगे बढ़ने से पहले आइए कुछ उदाहरणों पर गौर करते हैं।

दो समान वर्ण लेटकोड सॉल्यूशन के बीच सबसे बड़ा पदार्थ

s = "aa"
0

स्पष्टीकरण: इनपुट में दो 'ए' हैं और उनके बीच का तार लगाए गए स्थितियों को संतुष्ट करने वाला सबसे लंबा विकल्प है। इस प्रकार, आउटपुट सही है।

s = "abca"
2

स्पष्टीकरण: इनपुट स्ट्रिंग में कम से कम दो उदाहरणों वाले एकल वर्ण मौजूद हैं। तो, इष्टतम आउटपुट में "bc" होगा।

दो समान वर्णों के बीच सबसे बड़े पदार्थ लेटेकोड समाधान के लिए दृष्टिकोण

समस्या का हल दो सबसे बड़े वर्ण लेटकोड सॉल्यूशन के बीच का सबसे बड़ा पदार्थ समझना आसान है। समस्या में, हमें केवल सबसे बड़े सबरिंग की लंबाई खोजने के लिए कहा जाता है, लेकिन स्ट्रिंग ही नहीं। इसलिए, हम केवल दो एरे बनाते हैं जो किसी भी वर्ण के पहले और अंतिम इंडेक्स को स्टोर करते हैं। प्रारंभ में, हम इन सरणियों को -1 से भरते हैं जो एक चरित्र की घटना को नहीं दर्शाता है। एक बार जब हमें कोई ऐसा पात्र मिल जाता है तो हम इंडेक्स को पहले एरे में स्टोर कर लेते हैं यदि यह -1 से भरा हुआ है। यदि इसके पास -1 नहीं है, तो हम दूसरे ऐरे में इंडेक्स को स्टोर करते हैं।

इन दो सरणियों का उपयोग करते हुए, हम अधिकतम लंबाई पाते हैं। हम 0 से शुरू होने वाले एक लूप को चलाते हैं जब तक कि 25 सभी सरणियों के सभी सूचकांकों की जांच नहीं करते। यदि सूचक मान्य हैं, तो हम प्रत्येक पुनरावृत्ति में उत्तर को अपडेट करते हैं। अंत में, हम जवाब वापस करते हैं।

दो समान वर्ण लेटकोड सॉल्यूशन के बीच सबसे बड़े पदार्थ के लिए कोड

C ++ कोड

#include <bits/stdc++.h>
using namespace std;

int maxLengthBetweenEqualCharacters(string s) {
    vector<int> f1(26, -1), f2(26, -1);
    int n = s.size();
    for(int i=0;i<n;i++){
        if(f1[s[i]-'a'] == -1)
            f1[s[i]-'a'] = i;
        else
            f2[s[i]-'a'] = i;
    }

    int ans = -1;
    for(int i=0;i<26;i++)
        if(f2[i] != -1)
            ans = max(ans, f2[i]-f1[i]-1);
    return ans;
}

int main(){
    cout<<maxLengthBetweenEqualCharacters("aa");
}
0

जावा कोड

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
  public static int maxLengthBetweenEqualCharacters(String s) {
        int[] f1 = new int[26];
        int[] f2 = new int[26];
        for(int i=0;i<26;i++){
            f1[i] = -1;
            f2[i] = -1;
        }
        int n = s.length();
        for(int i=0;i<n;i++){
            if(f1[s.charAt(i)-'a'] == -1)
                f1[s.charAt(i)-'a'] = i;
            else
                f2[s.charAt(i)-'a'] = i;
        }
        
        int ans = -1;
        for(int i=0;i<26;i++)
            if(f2[i] != -1)
                ans = Math.max(ans, f2[i]-f1[i]-1);
        return ans;
    }
    
  public static void main (String[] args) throws java.lang.Exception
  {
    String s = "aa";
    System.out.print(maxLengthBetweenEqualCharacters(s));
  }
}
0

जटिलता विश्लेषण

समय जटिलता

पर), क्योंकि पूरे इनपुट स्ट्रिंग को पार करते हैं।

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

ओ (1), क्योंकि हमने निरंतर आकार सरणियों का उपयोग किया था।