Last Updated: 22 Aug, 2021
Longest Even Length Substring
Moderate
Asked in company
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.
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
Approaches
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 :
- Create a variable (say, ‘RES’) which will store the maximum length of the substring.
- 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’.
- 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.
- Finally, return ‘RES’.
The approach is to maintain an array to calculate the left sum and right sum in constant time. We create a sum array and store the prefix sum in it. Then for each element of the string, we generate a substring and calculate the left half and right half sum.
How to get the left half and right half sum using the prefix sum array?
Let the starting and ending points of a substring be ‘i’ and ‘j’ and ‘MID’ be the midpoint of the current substring.
Then left half sum will be : Sum till midpoint of substring - sum till starting point of a substring, i.e. ‘SUM[MID]’ - ‘SUM[i]’.
Similarly, we can find the right half sum using the substring's ‘MID’ and ending point (‘j’).
Here is the algorithm :
- Create an array (say, ‘SUM’) of size ‘N’ + 1 which will store the sum and initialize it with 0, where ‘N’ is the length of the substring.
- Run a loop from 1 to ‘N’ (say, iterator ‘i’) and update ‘SUM[i]’ as sum ‘SUM[i - 1]’ and ‘ith’ digit of the string.
- Create a variable (say, ‘RES’) which will store the maximum length of the substring.
- Run a loop from 0 to ‘N’ - 2 (say, iterator ‘i’).
- Run a loop from ‘i’ + 1 to ‘N’ (say iteration ‘j’) with incrementing ‘j’ with 2 after each iteration.
- Create a variable (say, ‘CURR’), which will store the current length of the substring and initialize it with ‘j’ - ‘i’ + 1.
- Create a variable (say, ‘MID’), which will serve as the middle index of the substring and initialize it with ‘i’ + ‘CURR/2’.
- Check if ‘SUM[MID]’ - ‘SUM[i]’ is equal to ‘SUM[j + 1]’ - ‘SUM[MID]’ and ‘RES’ is smaller than ‘CURR’, update ‘RES’ with ‘CURR’.
- Run a loop from ‘i’ + 1 to ‘N’ (say iteration ‘j’) with incrementing ‘j’ with 2 after each iteration.
- Finally, return ‘RES’.
The approach is to consider every element of the string as the midpoint of the substring and then expand the substring while calculating the left half and right half sum.
Here is the algorithm :
- Create a variable (say, ‘RES’) which will store the maximum length of the substring.
- Run a loop from 0 to ‘N’ - 2 (say, iterator ‘i’) where ‘N’ is the length of the substring.
- Create variables (say, ‘LOW’ and ‘HIGH’) that will expand both sides to find the left half and right half sum and initialize them with ‘i’ and ‘i’ + 1.
- Create variables (say, ‘lSum’ and ‘rSum’) that will store the left half and right half sum.
- Run a loop till ‘LOW’ is greater than equal to 0 and ‘HIGH’ smaller than ‘N’.
- Add digits in ‘lSum’ and ‘rSum’.
- Check if ‘lSum’ is equal to ‘rSum’, update ‘RES’ as maximum of ‘RES’ and ‘HIGH’ - ‘LOW’ + 1.
- Update ‘HIGH’ as ‘HIGH’ + 1 and ‘LOW’ as ‘LOW’ - 1.
- Finally, return ‘RES’.
Similar problems