To find the longest substring with equal sum in left and right in C++

Question

I was solving a question, with which I am having some problems:

Complete the function getEqualSumSubstring, which takes a single argument. The single argument is a string s, which contains only non-zero digits. This function should print the length of longest contiguous substring of s, such that the length of the substring is 2*N digits and the sum of the leftmost N digits is equal to the sum of the rightmost N digits. If there is no such string, your function should print 0.

int getEqualSumSubstring(string s) {
int i=0,j=i,foundLength=0;
    for(i=0;i<s.length();i++)
    {
        for(j=i;j<s.length();j++)
        {
            int temp = j-i;
            if(temp%2==0)
            {
                int leftSum=0,rightSum=0;
                string tempString=s.substr(i,temp);
                for(int k=0;k<temp/2;k++)
                {
                    leftSum=leftSum+tempString[k]-'0';
                    rightSum=rightSum+tempString[k+(temp/2)]-'0';
                }
                if((leftSum==rightSum)&&(leftSum!=0))
                    if(s.length()>foundLength)
                    foundLength=s.length(); 
            }
        }
    }
    return(foundLength);

}

The problem is that this code is working for some samples and not for the others. Since this is an exam type question I don't have the test cases either.

Answer 1

This code works

int getEqualSumSubstring(string s) {
    int i=0,j=i,foundLength=0;
    for(i=0;i<s.length();i++)
    {
        for(j=i;j<s.length();j++)
        {
            int temp = j-i+1;

            if(temp%2==0)
            {
                int leftSum=0,rightSum=0;
                string tempString=s.substr(i,temp);
                // printf("%d ",tempString.length());
                for(int k=0;k<temp/2;k++)
                {
                    leftSum=leftSum+tempString[k]-48;
                    rightSum=rightSum+tempString[k+(temp/2)]-48;
                }
                if((leftSum==rightSum)&&(leftSum!=0))
                    if(tempString.length()>foundLength)
                    foundLength=tempString.length(); 
            }
        }
    }
    return(foundLength);
}

The temp variable must be j-i+1. Otherwise the case where the whole string is the answer will not be covered. Also, we need to make the change suggested by Scott.

Answer 2

Here's my solution that I can confirm works. The ones above didn't really work for me - they gave me compile errors somehow. I got the same question on InterviewStreet, came up with a bad, incomplete solution that worked for 9/15 of the test cases, so I had to spend some more time coding afterwards.

The idea is that instead of caring about getting the left and right sums (which is what I initially did as well), I will get all the possible substrings out of each half (left and right half) of the given input, sort and append them to two separate lists, and then see if there are any matches.

Why?

Say the strings "423" and "234" have the same sum; if I sorted them, they would both be "234" and thus match. Since these numbers have to be consecutive and equal length, I no longer need to worry about having to add them up as numbers and check.

So, for example, if I'm given 12345678, then on the left side, the for-loop will give me:

[1,12,123,1234,2,23,234,3,34]

And on the right:

[5,56,567,5678,...]

And so forth.

However, I'm only taking substrings of a length of at least 2 into account.

I append each of these substrings, sorted by converting into a character array then converting back into a string, into ArrayLists.

So now that all this is done, the next step is to see if there are identical strings of the same numbers in these two ArrayLists. I simply check each of temp_b's strings against temp_a's first string, then against temp_a's second string, and so forth.

If I get a match (say, "234" and "234"), I'll set the length of those matching substrings as my tempCount (tempCount = 3). I also have another variable called 'count' to keep track of the greatest length of these matching substrings (if this was the first occurrence of a match, then count = 0 is overwritten by tempCount = 3, so count = 3).

As for the odd/even string length with the variable int end, the reason for this is because in the line of code s.length()/2+j, is the length of the input happened to be 11, then:

s.length() = 11

s.length()/2 = 11/5 = 5.5 = 5

So in the for-loop, s.length()/2 + j, where j maxes out at s.length()/2, would become:

5 + 5 = 10

Which falls short of the s.length() that I need to reach for to get the string's last index.

This is because the substring function requires an end index of one greater than what you'd put for something like charAt(i).

Just to demonstrate, an input of "47582139875" will generate the following output: [47, 457, 4578, 24578, 57, 578, 2578, 58, 258, 28] <-- substrings from left half [139, 1389, 13789, 135789, 389, 3789, 35789, 789, 5789, 578] <-- substrings from right half 578 <-- the longest one that matched 6 <-- the length of '578' x 2

public static int getEqualSumSubtring(String s){

    // run through all possible length combinations of the number string on left and right half
    // append sorted versions of these into new ArrayList

    ArrayList<String> temp_a = new ArrayList<String>();
    ArrayList<String> temp_b = new ArrayList<String>();

    int end; // s.length()/2 is an integer that rounds down if length is odd, account for this later 

    for( int i=0; i<=s.length()/2; i++ ){
        for( int j=i; j<=s.length()/2; j++ ){
            // only account for substrings with a length of 2 or greater
            if( j-i > 1 ){ 
                char[] tempArr1 = s.substring(i,j).toCharArray();
                Arrays.sort(tempArr1);
                String sorted1 = new String(tempArr1);
                temp_a.add(sorted1);
                //System.out.println(sorted1);

                if( s.length() % 2 == 0 )
                    end = s.length()/2+j;
                else // odd length so we need the extra +1 at the end
                    end = s.length()/2+j+1; 
                char[] tempArr2 = s.substring(i+s.length()/2, end).toCharArray();
                Arrays.sort(tempArr2);
                String sorted2 = new String(tempArr2);
                temp_b.add(sorted2);
                //System.out.println(sorted2);
            }

        }

    }

    // For reference
    System.out.println(temp_a);
    System.out.println(temp_b);

    // If the substrings match, it means they have the same sum

    // Keep track of longest substring
    int tempCount = 0 ;
    int count = 0;
    String longestSubstring = "";

    for( int i=0; i<temp_a.size(); i++){
        for( int j=0; j<temp_b.size(); j++ ){
            if( temp_a.get(i).equals(temp_b.get(j)) ){

                tempCount = temp_a.get(i).length();

                if( tempCount > count ){
                    count = tempCount;
                    longestSubstring = temp_a.get(i);

                }
            }

        }
    }

    System.out.println(longestSubstring);
    return count*2;
}