Longest even Length Substring such that Sum of First and Second Half is same

Problem: Given a large number in form of string having elements in range 0-9, i.e.12327668. Find the longest even length substring such that sum of elements of first half is equal to the sum of elements of second half.

For example:

Input: str = "123123"
Output: 6
The longest possible substring is "123123"

Input: str = "1253081"
Output: 4
The longest possible substring is "5308"

We have various approaches to solve this problem.

Method 1: A Naive Solution is to check every substring of even length. The following is C based implementation of simple approach.

#include<bits/stdc++.h>
using namespace std;

/* function returns the required result */
int evenLength(string s)
{
    int n = s.length();
    int max_len = -1;

    /* Choose starting point of every substring */
    for (int i=0; i<n; i++)
    {
        /* Choose ending point of even length substring */
        for (int j =i+1; j<n; j += 2)
        {
            /* Find length of current substr */
            int len = j-i+1;

            /* Calculating left & right sums for current substr */
            int lsum = 0, rsum =0;
            for (int k =0; k<len/2; k++)
            {
                lsum  += (s[i+k]-'0');
                rsum += (s[i+k+len/2]-'0');
            }

            /* Update max_len if needed */
            if (lsum == rsum)
                    max_len = max(max_len, len);
        }
    }
    return max_len;
}

/* driver function */
int main()
{
    string s = "123321";

    cout<<"The length of substring is: "<<evenLength(s)<<"\n";

    return 0;
}

Output:

The length of substring is: 6

Time Complexity: O(n³)

Method 2: Dynamic approach

#include<bits/stdc++.h>
using namespace std;

int evenLength(string s)
{
    int n = s.length();
    int sum[n][n], max_len = -1;
    
    for(int i = 0 ; i < n; i++)
        sum[i][i]= (s[i] - '0');

    /* considering all even length substrings one by one */
    for (int l = 2;l<=n;l++)
    {
        /* This is the starting index of your substring */
        for (int i = 0; i <= n-l; i++)
        {
            /* This is end point of the substring */
            int j = i + l - 1;

            /* This is middle point of substring */
            int k = i + (l/2) - 1;


            /* Finding total sum of the substring from
               previous memorized states */
            sum[i][j] = sum[i][k]+sum[k+1][j];

            /* if sum of first and second half is same than update max_len */
            if(l%2==0 && (sum[i][k] == sum[k+1][j]))
                max_len = max(max_len , l);
        }
    }

    return max_len;
}

/* driver function */
int main()
{
    string s = "123321";

    cout<<"The length of substring is: "<<evenLength(s)<<"\n";

    return 0;
}

Output:

The length of substring is: 6

Time Complexity: O(n²) and Space Complexity: O(n²)

Method 3: In this method first we calculate the cumulative sum and store in array. And later use the cumulative array.

#include <bits/stdc++.h>
using namespace std;

/* function returns the required result */
int evenLength(string s)
{
    /* cumulative array to store sum */
    int sum[s.length() + 1];
    sum[0] = 0;

    /* Calculating the cumulative array */
    for (int i = 1; i <= s.length(); i++)
    {
        sum[i] = sum[i - 1] + (s[i-1] - '0');
    }

    int max_len = -1, cur_len, lsum, rsum;

    /* considering all even length substrings one by one */
    for(int i=2; i<=s.length(); i=i+2)
    {
        cur_len = i;
        for(int j = 0; j <= (s.length() - cur_len + 1); j++)
        {
            /* Calculating lsum and rsum */
            lsum = sum[j + cur_len/2] - sum[j];
            rsum = sum[j + cur_len] - sum[j + cur_len/2];

            /* if sum of first and second half is same than update max_len */
            if(lsum == rsum)
                max_len = max(max_len, cur_len);
        }
    }

    return max_len;
}

int main()
{
    string s = "123321";

    cout<<"The length of substring is: "<<evenLength(s)<<"\n";

    return 0;
}

Output:

The length of substring is: 6

Time Complexity: O(n²) and Space Complexity: O(n)