Највећи подниз између решења са једнаким знаковима Леетцоде решење


Ниво тешкоће Лако
низ

Проблем Највећи подниз између два једнака знака Леетцоде решење, тражи да пронађемо дужину највећег подниза. Овде се подстринг намеће услов. Подниз би требао бити између истих знакова. Дакле, низ мора садржавати најмање два једнака знака како би излаз био природан број, иначе се -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), јер смо користили низове константне величине.