Бузургтарин Substring байни ду аломатҳои баробар Solution Leetcode


Сатҳи душворӣ осон
сатр

Мушкилоти калонтарин байни ду аломатҳои ҳалли Leetcode, аз мо хоҳиш мекунад, ки дарозии сатри калонтаринро пайдо кунем. Дар ин ҷо, ба зери сатр шарт гузошта шудааст. Сатр бояд дар байни аломатҳои якхела бошад. Ҳамин тавр, данд бояд ҳадди аққал ду аломати баробар дошта бошад, то натиҷа адади натуралии else -1 баргардонида шавад. Аммо пеш аз ҳалли масъала ба биёед якчанд мисолро дида бароем.

Бузургтарин Substring байни ду аломатҳои баробар Solution Leetcode

s = "aa"
0

Шарҳ: Вуруд ду 'а' -ро дар бар мегирад ва сатри байни онҳо сатри дарозтаринест, ки шароити гузошташударо қонеъ мекунад. Ҳамин тариқ, натиҷа дуруст аст.

s = "abca"
2

Шарҳ: Танҳо як аломат вуҷуд дорад, ки ҳадди ақал ду мисол дар сатри вуруд дошта бошад. Пас, натиҷаи оптималӣ "bc" -ро дар бар мегирад.

Равиш барои калонтарин сатр дар байни ду аломатҳои ҳалли Leetcode

Ҳалли мушкилот Субтринги калонтарин дар байни ду аломатҳои баробар Solitode Solution-ро дарк кардан осон аст. Дар ин масъала, аз мо танҳо хоҳиш карда мешавад, ки дарозии сатри калонтаринро ёбем, аммо худи сатрро не. Ҳамин тавр, мо танҳо ду массиви эҷод мекунем, ки индекси аввал ва охирини ягон аломатро нигоҳ медоранд. Дар аввал, мо ин массивҳоро бо -1 пур мекунем, ки рух додани аломатро ифода намекунад. Пас аз пайдо кардани аломат, мо индексро дар массиви аввал нигоҳ медорем, агар он бо -1 пур карда шуда бошад. Агар он -1 надошта бошад, мо индексро дар массиви дуюм нигоҳ медорем.

Бо истифода аз ин ду массив, мо дарозии максималиро меёбем. Мо давраеро оғоз мекунем, ки аз 0 то 25 сар карда, ҳамаи индекси ҳарду массивро месанҷад. Мо ҷавобро дар ҳар як такрор такмил медиҳем, агар нишондиҳандаҳо дуруст бошанд. Дар охир, мо ҷавобро бармегардонем.

Рамз барои калонтарин сатр дар байни ду аломатҳои баробар Solution Leetcode

Коди 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

Рамзи Java

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), зеро тамоми сатри вурудро убур кунед.

Мураккабии фазо

О (1), зеро мо массивҳои андозаи доимиро истифода мебурдем.