दोन समान वर्णांमधील सर्वात मोठे सबस्ट्रिंग लीटकोड सोल्यूशन


अडचण पातळी सोपे
अक्षरमाळा

दोन समान वर्णांमधील सर्वात मोठी सबस्ट्रिंग लीटकोड सोल्यूशन, आम्हाला सर्वात मोठ्या सबस्ट्रिंगची लांबी शोधण्यास सांगते. येथे सबस्ट्रिंगवर एक अट घातली आहे. सबस्ट्रिंग समान वर्णांमधील असावे. तर, द स्ट्रिंग कमीतकमी दोन समान अक्षरे असणे आवश्यक आहे जेणेकरून आउटपुट एक नैसर्गिक संख्या असेल अन्यथा -1 परत येईल. पण सोल्यूशन पुढे जाण्यापूर्वी काही उदाहरणे पाहूया.

दोन समान वर्णांमधील सर्वात मोठे सबस्ट्रिंग लीटकोड सोल्यूशन

s = "aa"
0

स्पष्टीकरणः इनपुटमध्ये दोन 'अ' असतात आणि त्या दरम्यानची स्ट्रिंग लादलेल्या अटींचे समाधान करणारे सर्वात लांब स्ट्रस्ट्रिंग असते. हे आऊटपुट योग्य आहे.

s = "abca"
2

स्पष्टीकरणः इनपुट स्ट्रिंगमध्ये कमीतकमी दोन घटनांमध्ये एकच वर्ण आहे. तर, चांगल्या आउटपुटमध्ये "बीसी" असेल.

दोन समान वर्णांमधील लेटेकोड सोल्यूशनमधील सर्वात मोठ्या सबस्ट्रिंगसाठी दृष्टीकोन

लेझकोड सोल्यूशन दोन समान वर्णांमधील सर्वात मोठे सबस्ट्रिंग समस्येचे निराकरण समजून घेणे सोपे आहे. समस्येमध्ये, आम्हाला केवळ सर्वात मोठ्या सबस्ट्रिंगची लांबी शोधण्यास सांगितले जाते परंतु केवळ स्वतःची स्ट्रिंगच नाही. तर, आम्ही फक्त दोन अ‍ॅरे तयार करतो जी कोणत्याही अक्षराचा पहिला आणि शेवटचा निर्देशांक संग्रहित करते. सुरुवातीस, आम्ही हे अ‍ॅरे -1 भरतो जे वर्ण नसल्याचे दर्शवितो. एकदा आम्हाला एखादे अक्षर सापडले की अनुक्रमणिका -1 भरली असल्यास प्रथम अ‍ॅरेमध्ये अनुक्रमांक ठेवतो. जर त्यात -1 नसेल तर आम्ही अनुक्रमणिका दुसर्‍या अ‍ॅरेमध्ये संचित करतो.

या दोन अ‍ॅरेचा वापर करून, आम्हाला कमाल लांबी सापडते. दोन्ही अ‍ॅरेची सर्व निर्देशांकांची तपासणी करत 0 पासून 25 पर्यंत सुरू असलेला लूप चालवितो. निर्देशांक वैध असल्यास आम्ही प्रत्येक पुनरावृत्तीमध्ये उत्तर अद्यतनित करतो. शेवटी, आम्ही उत्तर परत करतो.

दोन समान वर्णांमधील लेटेकोड सोल्यूशन दरम्यान सर्वात मोठ्या सबस्ट्रिंगसाठी कोड

सी ++ कोड

#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), कारण आम्ही स्थिर आकाराचे अ‍ॅरे वापरले.