दुई बराबर पात्रहरूको बीचको सबस्ट्रिring्ग लेटकोड समाधान


कठिनाई तह सजिलो
घागो

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

दुई बराबर पात्रहरूको बीचको सबस्ट्रिring्ग लेटकोड समाधान

s = "aa"
0

स्पष्टीकरण: इनपुटले दुई 'a' समावेश गर्दछ र तिनीहरू बीचको स्ट्रि the लागू गरिएको सर्तहरू पूरा गर्ने सबैभन्दा लामो सब्सट्रि be हुन्छ। यसरी आउटपुट सहि छ।

s = "abca"
2

स्पष्टीकरण: इनपुट स्ट्रि inमा कम्तिमा दुई उदाहरणहरू भएको एक मात्र चरित्र अवस्थित छ। त्यसो भए, अधिकतम आउटपुटमा "bc" समावेश हुन्छ।

दुई बराबर वर्णहरूको बीचको सबस्ट्रिring्गको लागि दृष्टिकोण ल्याटकोड समाधान

समस्याको समाधान दुई बराबर अक्षरहरूको बीचमा सबस्ट्रिring्ग Leetcode समाधान बुझ्नको लागि सजिलो छ। समस्यामा, हामीलाई केवल सबैभन्दा ठूलो सबस्ट्रिंगको लम्बाइ पत्ता लगाउन भनियो तर स्ट्रिंग आफैंमा होइन। त्यसो भए, हामी केवल दुई एर्रेहरू सिर्जना गर्छौं जुन कुनै पनि क्यारेक्टरको पहिलो र अन्तिम सूचकांक भण्डार गर्दछ। प्रारम्भमा, हामी यी एरेहरू भरिन्छौं -१ जसले क्यारेक्टरको घटनालाई सूचित गर्दैन। एकचोटि हामीले कुनै वर्ण फेला पारेपछि अनुक्रमणिका पहिलो एरेमा भण्डार गर्छौं यदि यो -१ भरिएको छ भने। यदि त्यो -1 छैन भने, हामी दोस्रो एरेमा अनुक्रमणिका भण्डार गर्दछौं।

यी दुई एर्रेहरू प्रयोग गरेर हामी अधिकतम लम्बाई फेला पार्दछौं। हामी दुबै एर्रेको सबै सूचकांकहरू जाँच गर्दै ० देखि २ 0 सम्म लूप चलाउँछौं। हामी प्रत्येक पुनरावृत्तिमा उत्तर अपडेट गर्छौं यदि सूचकहरू मान्य छन्। अन्तमा, हामी जवाफ फर्काउँछौं।

दुई बराबर वर्णहरूको बीचको सबस्ट्रिringको लागि कोड Leetcod समाधान

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

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

समय जटिलता

O (N), किनकि सम्पूर्ण इनपुट स्ट्रि tra ट्रान्सवर्स गर्नुहोस्।

ठाउँ जटिलता

O (१), किनकि हामीले निरन्तर साइज एर्रे प्रयोग गर्‍यौं।