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

Longest Even Length Substring such that Sum of First and Second Half is same - Searching and Sorting - Given a string ‘str’ of digits, find length of the longest substring of ‘str’, such that the length of the substring is 2k digits.

Given a string ‘str’ of digits, find length of the longest substring of ‘str’, such that the length of the substring is 2k digits and sum of left k digits is equal to the sum of right k digits.

Examples:

```Input: str = "123123"
Output: 6
The complete string is of even length and sum of first and second
half digits is same

Input: str = "1538023"
Output: 4
The longest substring with same first and second half sum is "5380"
```

Simple Solution [ O(n3) ]
A Simple Solution is to check every substring of even length. The following is C based implementation of simple approach.

C
``````// A simple C based program to find length of longest  even length
// substring with same sum of digits in left and right
#include<stdio.h>
#include<string.h>

int findLength(char *str)
{
int n = strlen(str);
int maxlen =0;  // Initialize result

// 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)
{
int length = j-i+1;//Find length of current substr

// Calculate left & right sums for current substr
int leftsum = 0, rightsum =0;
for (int k =0; k<length/2; k++)
{
leftsum  += (str[i+k]-'0');
rightsum += (str[i+k+length/2]-'0');
}

// Update result if needed
if (leftsum == rightsum && maxlen < length)
maxlen = length;
}
}
return maxlen;
}

// Driver program to test above function
int main(void)
{
char str[] = "1538023";
printf("Length of the substring is %d", findLength(str));
return 0;
}``````

Output:

`Length of the substring is 4` 