Largest Substring Between Two Equal Characters Leetcode Solution

The problem Largest Substring Between Two Equal Characters Leetcode Solution, asks us to find the length of the largest substring. Here, a condition is imposed on the substring. The substring should be between the same characters. So, the string must contain at least two equal characters so that the output happens to be a natural number else -1 is returned. But before moving ahead with the solution let us take a look at a few examples.

s = "aa"

0

Explanation: The input contains two ‘a’s and the string between them happens to be the longest substring satisfying the imposed conditions. Thus, the output is correct.

s = "abca"

2

Explanation: There exists only a single character having at least two instances in the input string. So, the optimal output will contain “bc”.

Approach for Largest Substring Between Two Equal Characters Leetcode Solution

The solution for the problem Largest Substring Between Two Equal Characters Leetcode Solution is easy to understand. In the problem, we are only asked to find the length of the largest substring but not the string itself. So, we simply create two arrays that store the first and last index of any character. Initially, we fill these arrays with -1 which denotes no occurrence of a character. Once we find a character we store the index in the first array if it is filled with -1. If that does not have -1, we store the index in the second array.

Using these two arrays, we find the maximum length. We run a loop starting from 0 until 25 checking all the indices of both the arrays. We update the answer in each iteration if the indices are valid. In the end, we return the answer.

Code for Largest Substring Between Two Equal Characters Leetcode Solution

C++ code

#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 code

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

Complexity Analysis

Time Complexity

O(N), because traverse the entire input string.

Space Complexity

O(1), because we used constant size arrays.