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

Longest Even Length Substring such that Sum of First and Second Half is same - GeeksforGeeks
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
O(N^2):  The idea is to build a 2D table that stores sums of substrings.

int findLength(char *str)

{

    int n = strlen(str);

    int maxlen = 0; // Initialize result

 

    // A 2D table where sum[i][j] stores sum of digits

    // from str[i] to str[j].  Only filled entries are

    // the entries where j >= i

    int sum[n][n];

 

    // Fill the diagonal values for sunstrings of length 1

    for (int i =0; i<n; i++)

        sum[i][i] = str[i]-'0';

 

    // Fill entries for substrings of length 2 to n

    for (int len=2; len<=n; len++)

    {

        // Pick i and j for current substring

        for (int i=0; i<n-len+1; i++)

        {

            int j = i+len-1;

            int k = len/2;

 

            // Calculate value of sum[i][j]

            sum[i][j] = sum[i][j-k] + sum[j-k+1][j];

 

            // Update result if 'len' is even, left and right

            // sums are same and len is more than maxlen

            if (len%2 == 0 && sum[i][j-k] == sum[(j-k+1)][j]

                           && len > maxlen)

                 maxlen = len;

        }

    }

    return maxlen;

}

O(N^3): A Simple Solution is to check every substring of even length.

int findLength(char *str)

{

    int n = strlen(str);

    int maxlen =0;  // Initialize result

 

    // Choose starting point of every substring

    for (int i=0; i<n; i++)

    {

        // Choose ending point of even length substring

        for (int j =i+1; j<n; j += 2)

        {

            int length = j-i+1;//Find length of current substr

 

            // Calculate left & right sums for current substr

            int leftsum = 0, rightsum =0;

            for (int k =0; k<length/2; k++)

            {

                leftsum  += (str[i+k]-'0');

                rightsum += (str[i+k+length/2]-'0');

            }

 

            // Update result if needed

            if (leftsum == rightsum && maxlen < length)

                    maxlen = length;

        }

    }

    return maxlen;

}

Read full article from Longest Even Length Substring such that Sum of First and Second Half is same - GeeksforGeeks