Longest substring between any pair of occurrences ōf similar characters

0 0 4 minutes read

Given a string S, the task is to find the length of the longest substring between any pair of occurrences of same character.

Examples:

Input: S = “accabbacc”
Output: 6
Explanation: The longest substring satisfying the required conditions is “cabbac”, which lies between S[1](= ‘c’) and s[8](= ‘c’).

Input: S = “aab”
Output: 0

Approach: Follow the steps below to solve the problem:

Initialize two variables res and diff to store the length of the longest substring and the length of the current substring between pair of same characters respectively.
Iterate over characters of the string from left to right.
Iterate over the remaining string on the right, from right to left up to the current character.
If two equal characters are obtained, i.e. S[i] = S[j], , store the length of the substring between them in diff.
Update the value of res as max(res, diff). so that res stores the longest substring of required type obtained so far.
After complete traversal of the string, print res as the required answer.

Below is the implementation of the above approach:

C++

// C++ program to implement
// the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the longest substring
// between pair of repetitions of the same character
int longestbetweenequalcharacters(string S)
{
 
    // Length of the string
    int n = S.length();
 
    // Stores the maximum length and
    // length of current substring
    // satisfying given conditions
    int res = -1, diff = -1;
 
    // Traverse the string
    for (int i = 0; i < n - 1; i++) {
 
        // Search for repetition of S[i]
        for (int j = n - 1; j > i; j--) {
 
            // If repetition occurs
            if (S[i] == S[j]) {
 
                // Store the length of
                // the substring
                diff = j - i - 1;
 
                // Update maximum length of
                // substring obtained
                res = max(diff, res);
            }
        }
    }
 
    // Return obtained maximum length
    return res;
}
 
// Driver Code
int main()
{
    string s = "accabbacc";
    cout << longestbetweenequalcharacters(s);
}

Java

// Java program to implement 
// the above approach 
class GFG{
      
// Function to find the longest substring
// between pair of repetitions of the 
// same character
static int longestbetweenequalcharacters(String S)
{
     
    // Length of the string
    int n = S.length();
  
    // Stores the maximum length and
    // length of current substring
    // satisfying given conditions
    int res = -1, diff = -1;
  
    // Traverse the string
    for(int i = 0; i < n - 1; i++)
    {
         
        // Search for repetition of S[i]
        for(int j = n - 1; j > i; j--)
        {
             
            // If repetition occurs
            if (S.charAt(i) == S.charAt(j))
            {
                 
                // Store the length of
                // the substring
                diff = j - i - 1;
  
                // Update maximum length of
                // substring obtained
                res = Math.max(diff, res);
            }
        }
    }
  
    // Return obtained maximum length
    return res;
}
  
// Driver code
public static void main(String[] args)
{
     
    String s = "accabbacc";
     
    System.out.println(
        longestbetweenequalcharacters(s));
}
}
 
// This code is contributed by code_hunt

Python3

# Python3 program to implement
# the above approach
 
# Function to find the longest
# substring between pair of 
# repetitions of the same character
def longestbetweenequalcharacters(S):
     
    # Length of the string
    n = len(S)
 
    # Stores the maximum length and
    # length of current substring
    # satisfying given conditions
    res = -1
    diff = -1
 
    # Traverse the string
    for i in range(n - 1):
         
        # Search for repetition of S[i]
        for j in range(n - 1, i, -1):
             
            # If repetition occurs
            if (S[i] == S[j]):
 
                # Store the length of
                # the substring
                diff = j - i - 1
 
                # Update maximum length of
                # substring obtained
                res = max(diff, res)
 
    # Return obtained maximum length
    return res
 
# Driver Code
if __name__ == '__main__':
     
    s = "accabbacc"
     
    print(longestbetweenequalcharacters(s))
 
# This code is contributed by doreamon_

C#

// C# program to implement
// the above approach  
using System;
 
class GFG{
       
// Function to find the longest substring
// between pair of repetitions of the 
// same character
static int longestbetweenequalcharacters(String S)
{
     
    // Length of the string
    int n = S.Length;
   
    // Stores the maximum length and
    // length of current substring
    // satisfying given conditions
    int res = -1, diff = -1;
   
    // Traverse the string
    for(int i = 0; i < n - 1; i++)
    {
         
        // Search for repetition of S[i]
        for(int j = n - 1; j > i; j--)
        {
             
            // If repetition occurs
            if (S[i] == S[j])
            {
                 
                // Store the length of
                // the substring
                diff = j - i - 1;
   
                // Update maximum length of
                // substring obtained
                res = Math.Max(diff, res);
            }
        }
    }
   
    // Return obtained maximum length
    return res;
}
   
// Driver code
public static void Main()
{
    string s = "accabbacc";
      
    Console.WriteLine(
        longestbetweenequalcharacters(s));
}
}
 
// This code is contributed by sanjoy_62

Javascript

<script>
 
// javascript program to implement 
// the above approach 
 
      
// Function to find the longest substring
// between pair of repetitions of the 
// same character
function longestbetweenequalcharacters(S)
{
     
    // Length of the string
    var n = S.length;
  
    // Stores the maximum length and
    // length of current substring
    // satisfying given conditions
    var res = -1, diff = -1;
  
    // Traverse the string
    for(i = 0; i < n - 1; i++)
    {
         
        // Search for repetition of S[i]
        for(j = n - 1; j > i; j--)
        {
             
            // If repetition occurs
            if (S.charAt(i) == S.charAt(j))
            {
                 
                // Store the length of
                // the substring
                diff = j - i - 1;
  
                // Update maximum length of
                // substring obtained
                res = Math.max(diff, res);
            }
        }
    }
  
    // Return obtained maximum length
    return res;
}
  
// Driver code
 
var s = "accabbacc";
 
document.write(
    longestbetweenequalcharacters(s));
 
// This code contributed by shikhasingrajput 
 
</script>

Output:

Time Complexity: O(N²)
Auxiliary Space: O(1)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!