Longest Even Length Substring

Moderate
0/80
profile
Contributed by
10 upvotes
Asked in company
Microsoft

Problem statement

Your team is participating in ICPC preliminaries. To qualify for the regional contest, you have to solve at least one problem of the competition. The easiest problem among them is that you have given a string ‘STR’ containing digits, and you have to find the longest substring of length 2P such that the sum of right ‘P’ elements and left ‘P’ elements are equal.

Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of input contains an integer ‘T’, the number of test cases.

The only line in each test contains the string ‘STR’.
Output Format : 
For each test case, print a single integer representing the length of the longest substring.

Print the output of each test case in a separate line.
Note : 
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 10
1 <= |STR| <= 100

Time Limit : 1 sec
Sample Input 1 :
2
1212
1538023
Sample Output 1 :
4
4
Explanation For Sample Input 1 :
For first test case :

The length of the string is 4 and the sum of the first half and second half is the same.


For second test case the graph will be :

The longest even length substring with left half sum same as right half sum is “5380”.
Hint

Check every even length substring.

Approaches (3)
Brute Force

The basic idea is to check every even length substring of ‘STR’ and check whether the left half sum is equal to the right half sum or not.

 

Here is the algorithm :
 

  1. Create a variable (say, ‘RES’) which will store the maximum length of the substring.
  2. Run a loop from 0 to ‘N - 1’ (say, iterator ‘i’), where ‘N’ is the length of string ‘STR’.
    • Run a loop from ‘i’ + 1 to ‘N’ (say, iterator ‘j’). Increment value of ‘j’ by 2 after every iteration as we have to check only for even length substring.
      • Create a variable (say, ‘CURR’) which will store the current length of the substring.
      • Create variables (say, ‘lSum’ and ‘rSum’) which will store the left half sum and right half sum of the substring.
      • Run a loop from 0 to ‘CURR/2’ (say, iterator ‘K’) and add digits in ‘lSum’ and ‘rSum’.
      • Check if ‘lSum’ is equal to ‘rSum’ and if ‘CURR’ is greater than ‘RES’, update ‘RES’ with ‘CURR’.
  3. Finally, return ‘RES’.
Time Complexity

O(N ^ 3), where ‘N’ is the length of the string.

 

For each element in the string we traverse the string again to generate an even length substring. And for each even length substring we calculate the right half sum and left half sum which can take time maximum upto O(N). Therefore, the overall time complexity will be O(N ^ 3).

Space Complexity

O(1)

 

We are not using any extra space. Therefore, the overall space complexity will be O(1).

Code Solution
(100% EXP penalty)
Longest Even Length Substring
Full screen
Console