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.
[pastacode lang=”c” manual=”%2F%2F%20A%20simple%20C%20based%20program%20to%20find%20length%20of%20longest%20%20even%20length%0A%2F%2F%20substring%20with%20same%20sum%20of%20digits%20in%20left%20and%20right%20%0A%23include%3Cstdio.h%3E%0A%23include%3Cstring.h%3E%0A%20%0Aint%20findLength(char%20*str)%0A%7B%0A%20%20%20%20int%20n%20%3D%20strlen(str)%3B%0A%20%20%20%20int%20maxlen%20%3D0%3B%20%20%2F%2F%20Initialize%20result%0A%20%0A%20%20%20%20%2F%2F%20Choose%20starting%20point%20of%20every%20substring%0A%20%20%20%20for%20(int%20i%3D0%3B%20i%3Cn%3B%20i%2B%2B)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20Choose%20ending%20point%20of%20even%20length%20substring%0A%20%20%20%20%20%20%20%20for%20(int%20j%20%3Di%2B1%3B%20j%3Cn%3B%20j%20%2B%3D%202)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20int%20length%20%3D%20j-i%2B1%3B%2F%2FFind%20length%20of%20current%20substr%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20Calculate%20left%20%26%20right%20sums%20for%20current%20substr%0A%20%20%20%20%20%20%20%20%20%20%20%20int%20leftsum%20%3D%200%2C%20rightsum%20%3D0%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20(int%20k%20%3D0%3B%20k%3Clength%2F2%3B%20k%2B%2B)%0A%20%20%20%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20leftsum%20%20%2B%3D%20(str%5Bi%2Bk%5D-‘0’)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20rightsum%20%2B%3D%20(str%5Bi%2Bk%2Blength%2F2%5D-‘0’)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20Update%20result%20if%20needed%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20(leftsum%20%3D%3D%20rightsum%20%26%26%20maxlen%20%3C%20length)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20maxlen%20%3D%20length%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%20%20%20return%20maxlen%3B%0A%7D%0A%20%0A%2F%2F%20Driver%20program%20to%20test%20above%20function%0Aint%20main(void)%0A%7B%0A%20%20%20%20char%20str%5B%5D%20%3D%20%221538023%22%3B%0A%20%20%20%20printf(%22Length%20of%20the%20substring%20is%20%25d%22%2C%20findLength(str))%3B%0A%20%20%20%20return%200%3B%0A%7D” message=”C” highlight=”” provider=”manual”/]
Output:
Length of the substring is 4
[ad type=”banner”]