Maximum Length of Sub-array with Same First and Last Elements in C++

In this problem, we are given an array of characters. Our task is to create a program to print the maximum length of the subarray whose first and last elements are same in C++.

Let’s take an example to understand the problem,

Input − array = {‘t’, ‘u’, ‘t’, ‘o’, ‘r’, ‘i’, ‘a’, ‘l’, ‘s’, ‘p’, ‘o’, ‘i’, ‘n’, ‘t’ }

Output − 14

Explanation −

The subarray {‘t’, ‘u’, ‘t’, ‘o’, ‘r’, ‘i’, ‘a’, ‘l’, ‘s’, ‘p’, ‘o’, ‘i’, ‘n’, ‘t’ } starts and ends with t.

To solve this problem, we find the first and last occurrence a character in the array and then using the formula −

subarray length = lastOccurrence - firstOccurrence + 1

We will find the maximum length of all outcomes.

Let’s solve an example to understand the solution,

Array = {a, b , a , c , b, a}

Element a , firstoccerrence at index 0, last occurrence at index 5

Subarray length = 5 - 0 + 1= 4

maxLength = 6

Element b , firstoccerrence at index 1, last occurrence at index 4

Subarray length = 4 - 1 + 1 = 4

maxLength = 6

Example

Program to print the maximum length of the subarray whose first and last elements are same −

 Live Demo

#include <iostream>
using namespace std;
int maxSubArrLength(string arr, int n){
   int firstOccurrence, lastOccurrence = -1;
   int maxlength = 0;
   char ch;
   for (int i = 0; i < n; i++){
      ch = arr[i];
      firstOccurrence = lastOccurrence = i;
      for(int j = i; j<n; j++){
         if(arr[j] == ch)
            lastOccurrence = j;
      }
      maxlength = max(maxlength, (lastOccurrence - firstOccurrence + 1));
   }
   return maxlength;
}
int main(){
   string arr = "tutorialsPoint";
   int n = arr.length();
   cout<<"The maximum length of subarray whose first and last elements are same is "<<maxSubArrLength(arr, n);
   return 0;
}

Output

The maximum length of subarray whose first and last elements are same is 14