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 characterint 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 Codeint 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 characterstatic 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 codepublic 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 characterdef 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 Codeif __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 characterstatic 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 codepublic 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 characterfunction 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 codevar s = "accabbacc";document.write( longestbetweenequalcharacters(s));// This code contributed by shikhasingrajput </script> |
Output:
6
Time Complexity: O(N2)
Auxiliary Space: O(1)
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
