Saturday, 12 November 2016

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

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"


Solution:

public class Solution{

public static void main(String [] args)
{
String val = "1538023";
int [][] dp = new int[val.length() ][val.length() ];

for(int i = 0 ; i < val.length(); i++){
dp[i][i] = Integer.valueOf(val.charAt(i));
}
int max = 0 ;
for(int c = 2 ; c < val.length() ; c++){
for(int i = 0 ; i < val.length() - c + 1 ; i++){
int j = i + c - 1;
int k = c / 2;
dp[i][j] = dp[i][j-1] + Integer.valueOf(val.charAt(j));
if(c % 2 == 0 && dp[i][j - k] == dp[j-k+1][j] && c > max){
max = c;
}


}
}
System.out.println(max);
}

}

No comments:

Post a Comment