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