兩個相等字符的Leetcode解決方案之間的最大子字符串


難度級別 容易獎學金

兩個相等字符Leetcode解決方案之間的最大子串問題,要求我們找出最大子串的長度。 在此,對子字符串施加條件。 子字符串應在相同字符之間。 所以 必須至少包含兩個相等的字符,以便輸出恰好是自然數,否則返回-1。 但是在繼續解決方案之前,讓我們看一些示例。

兩個相等字符的Leetcode解決方案之間的最大子字符串

s = "aa"
0

說明:輸入包含兩個'a',它們之間的字符串恰好是滿足施加條件的最長子字符串。 因此,輸出是正確的。

s = "abca"
2

說明:輸入字符串中僅存在一個具有至少兩個實例的字符。 因此,最佳輸出將包含“ bc”。

兩個相等字符Leetcode解決方案之間最大子串的處理方法

兩個相等字符之間的最大子字符串Leetcode解決方案問題的解決方案很容易理解。 在問題中,僅要求我們找到最大子字符串的長度,而不是字符串本身。 因此,我們只需創建兩個數組即可存儲任何字符的第一個和最後一個索引。 最初,我們用-1填充這些數組,這表示沒有字符出現。 找到字符後,如果索引用-1填充,則將其存儲在第一個數組中。 如果沒有-1,我們將索引存儲在第二個數組中。

使用這兩個數組,我們可以找到最大長度。 我們運行一個從0到25的循環,檢查兩個數組的所有索引。 如果索引有效,我們將在每次迭代中更新答案。 最後,我們返回答案。

兩個相等字符之間的最大子字符串的代碼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(1), 因為我們使用了恆定大小的數組。