I came across the following question: There is a string of numbers. You need to find out the longest substring of size 2K such that the sum of K elements from left equals to sum of K elements from right.
Output:4 (since 1221 is the longest substring of 31221684 that satisfies the conditions mentioned above and its length is 4)
My Solution: 1. create an array of size n. Each element of the array will contain the sum of all previous elements plus the current element. Eg: For input string: 31221684, the resultant array will be [3,4,6,8,9,15,23,27] 2. Iterate through a loop starting with largest even length possible all the way to 0 For each iteration take the length as window and slide it through the array created in step 1 For each slide calculate the sum of K elements from the left and sum of K elements from the right If they are equal then print the length and come out of all loops, if they are not equal continue looping 3. If it is unable to find the answer after all iteration print length as 0
tc = int(input()) while tc!=0: current_string = input() n = len(current_string) arr =  curr_sum = 0 for i in current_string: curr_sum += int(i) arr.append(curr_sum) if n%2 != 0: n = n-1 found = False for curr_string_len in range(n,0,-2): for position in range(curr_string_len-1, n): mid_left = position//2 left = position-curr_string_len left_sum = arr[mid_left] if left < 0 else arr[mid_left]-arr[left] right_sum = arr[position]-arr[mid_left] if left_sum == right_sum: print(curr_string_len) found = True break if found: break if not found: print(0) tc-=1
This Solution is O(n^2) time and O(n) space complexity. But this solution is not being accepted. So, can you provide me any competitive programming site with this question and it's solution (in python3) Or, suggest anything wrong with the solution? (Not GeeksForGeeks as it is the one not accepting the solution.)