Given a string ‘str’ of digits, find the 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"
Simple Solution [ O(n3) ]
A Simple Solution is to check every substring of even length. The following is the implementation of simple approach.
C++
// A simple C++ based program to find length of longest even length// substring with same sum of digits in left and right #include<bits/stdc++.h>using namespace std;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;}// Driver program to test above functionint main(void){ char str[] = "1538023"; cout << "Length of the substring is " << findLength(str); return 0;}// This code is contributed// by Akanksha Rai |
C
// A simple C based program to find length of longest even length// substring with same sum of digits in left and right #include<stdio.h>#include<string.h>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;}// Driver program to test above functionint main(void){ char str[] = "1538023"; printf("Length of the substring is %d", findLength(str)); return 0;} |
Java
// A simple Java based program to find // length of longest even length substring // with same sum of digits in left and right import java.io.*;class GFG {static int findLength(String str){ int n = str.length(); 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) { // Find length of current substr int length = j - i + 1; // Calculate left & right sums // for current substr int leftsum = 0, rightsum = 0; for (int k = 0; k < length/2; k++) { leftsum += (str.charAt(i + k) - '0'); rightsum += (str.charAt(i + k + length/2) - '0'); } // Update result if needed if (leftsum == rightsum && maxlen < length) maxlen = length; } } return maxlen;}// Driver program to test above functionpublic static void main(String[] args){ String str = "1538023"; System.out.println("Length of the substring is " + findLength(str));}}// This code is contributed by Prerna Saini |
Python3
# A simple Python 3 based# program to find length# of longest even length# substring with same sum# of digits in left and right def findLength(str): n = len(str) maxlen = 0 # Initialize result # Choose starting point # of every substring for i in range(0, n): # Choose ending point # of even length substring for j in range(i+1, n, 2): # Find length of current substr length = j - i + 1 # Calculate left & right # sums for current substr leftsum = 0 rightsum =0 for k in range(0,int(length/2)): leftsum += (int(str[i+k])-int('0')) rightsum += (int(str[i+k+int(length/2)])-int('0')) # Update result if needed if (leftsum == rightsum and maxlen < length): maxlen = length return maxlen# Driver program to# test above functionstr = "1538023"print("Length of the substring is", findLength(str))# This code is contributed by# Smitha Dinesh Semwal |
C#
// A simple C# based program to find // length of longest even length substring // with same sum of digits in left and right using System;class GFG {static int findLength(String str){ int n = str.Length; 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) { // Find length of current substr int length = j - i + 1; // 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;} // Driver program to test above function public static void Main() { String str = "1538023"; Console.Write("Length of the substring is " + findLength(str)); }}// This code is contributed by nitin mittal |
PHP
<?php// A simple PHP based program to find length of // longest even length substring with same sum // of digits in left and right function findLength($str){ $n = strlen($str); $maxlen = 0; // Initialize result // Choose starting point of every substring for ($i = 0; $i < $n; $i++) { // Choose ending point of even // length substring for ($j = $i + 1; $j < $n; $j += 2) { $length = $j - $i + 1; // Find length of current substr // Calculate left & right sums // for current substr $leftsum = 0; $rightsum = 0; for ($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;}// Driver Code$str = "1538023";echo("Length of the substring is ");echo(findLength($str));// This code is contributed// by Shivi_Aggarwal?> |
Javascript
<script>// A simple Javascript based program to find // length of longest even length substring // with same sum of digits in left and right function findLength(str) { let n = str.length; let maxlen = 0; // Initialize result // Choose starting point of every // substring for (let i = 0; i < n; i++) { // Choose ending point of even // length substring for (let j = i + 1; j < n; j += 2) { // Find length of current substr let length = j - i + 1; // Calculate left & right sums // for current substr let leftsum = 0, rightsum = 0; for (let k = 0; k < Math.floor(length/2); k++) { leftsum += (str[i+k] - '0'); rightsum += (str[i+k+Math.floor(length/2)] - '0'); } // Update result if needed if (leftsum == rightsum && maxlen < length) maxlen = length; } } return maxlen; } let str = "1538023"; document.write("Length of the substring is " + findLength(str)); // This code is contributed by rag2127 </script> |
Output
Length of the substring is 4
Dynamic Programming [ O(n2) and O(n2) extra space]
The above solution can be optimized to work in O(n2) using Dynamic Programming. The idea is to build a 2D table that stores sums of substrings. The following is the implementation of Dynamic Programming approach.
C++
// A C++ based program that uses Dynamic // Programming to find length of the// longest even substring with same sum // of digits in left and right half#include<bits/stdc++.h>using namespace std;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 // substrings 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;}// Driver Codeint main(void){ char str[] = "153803"; cout << "Length of the substring is " << findLength(str); return 0;} // This code is contributed// by Mukul Singh. |
C
// A C based program that uses Dynamic Programming to find length of the// longest even substring with same sum of digits in left and right half#include <stdio.h>#include <string.h>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 substrings 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;}// Driver program to test above functionint main(void){ char str[] = "153803"; printf("Length of the substring is %d", findLength(str)); return 0;} |
Java
// A Java based program that uses Dynamic // Programming to find length of the longest// even substring with same sum of digits // in left and right halfimport java.io.*;class GFG {static int findLength(String str){ int n = str.length(); 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[][] = new int[n][n]; // Fill the diagonal values for // substrings of length 1 for (int i = 0; i < n; i++) sum[i][i] = str.charAt(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;}// Driver program to test above functionpublic static void main(String[] args){ String str = "153803"; System.out.println("Length of the substring is " + findLength(str));}}// This code is contributed by Prerna Saini |
Python3
# Python3 code that uses Dynamic Programming # to find length of the longest even substring # with same sum of digits in left and right half def findLength(string): n = len(string) 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 Sum = [[0 for x in range(n)] for y in range(n)] # Fill the diagonal values for # substrings of length 1 for i in range(0, n): Sum[i][i] = int(string[i]) # Fill entries for substrings # of length 2 to n for length in range(2, n + 1): # Pick i and j for current substring for i in range(0, n - length + 1): j = i + length - 1 k = length // 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 (length % 2 == 0 and Sum[i][j - k] == Sum[(j - k + 1)][j] and length > maxlen): maxlen = length return maxlen # Driver Codeif __name__ == "__main__": string = "153803" print("Length of the substring is", findLength(string)) # This code is contributed # by Rituraj Jain |
C#
// A C# based program that uses Dynamic // Programming to find length of the longest// even substring with same sum of digits // in left and right halfusing System;class GFG {static int findLength(String str){ int n = str.Length; 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 = new int[n, n]; // Fill the diagonal values for // substrings 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;}// Driver program to test above functionpublic static void Main(){ String str = "153803"; Console.WriteLine("Length of the substring is " + findLength(str));}}// This code is contributed // by Akanksha Rai(Abby_akku) |
PHP
<?php// A PHP based program that uses Dynamic // Programming to find length of the longest// even substring with same sum of digits// in left and right halffunction findLength($str){ $n = strlen($str); $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 // Fill the diagonal values for // substrings of length 1 for ($i = 0; $i < $n; $i++) $sum[$i][$i] = $str[$i] - '0'; // Fill entries for substrings of // length 2 to n for ($len = 2; $len <= $n; $len++) { // Pick i and j for current substring for ($i = 0; $i < $n - $len + 1; $i++) { $j = $i + $len - 1; $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;}// Driver Code$str = "153803";echo("Length of the substring is "); echo(findLength($str));// This code is contributed// by Shivi_Aggarwal?> |
Javascript
<script>// A javascript based program that uses Dynamic // Programming to find length of the longest// even substring with same sum of digits // in left and right halffunction findLength(str){ var n = str.length; var 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 var sum = Array(n).fill(0).map(x => Array(n).fill(0)); // Fill the diagonal values for // substrings of length 1 for (i = 0; i < n; i++) sum[i][i] = str.charAt(i).charCodeAt(0) - '0'.charCodeAt(0); // Fill entries for substrings of // length 2 to n for (len = 2; len <= n; len++) { // Pick i and j for current substring for (i = 0; i < n - len + 1; i++) { var j = i + len - 1; var k = parseInt(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;}// Driver program to test above functionvar str = "153803";document.write("Length of the substring is " + findLength(str));// This code contributed by shikhasingrajput </script> |
Output
Length of the substring is 4
Time complexity of the above solution is O(n2), but it requires O(n2) extra space.
[A O(n2) and O(n) extra space solution]
The idea is to use a single dimensional array to store cumulative sum.
C++
// A O(n^2) time and O(n) extra space solution#include<bits/stdc++.h>using namespace std;int findLength(string str, int n){ int sum[n+1]; // To store cumulative sum from first digit to nth digit sum[0] = 0; /* Store cumulative sum of digits from first to last digit */ for (int i = 1; i <= n; i++) sum[i] = (sum[i-1] + str[i-1] - '0'); /* convert chars to int */ int ans = 0; // initialize result /* consider all even length substrings one by one */ for (int len = 2; len <= n; len += 2) { for (int i = 0; i <= n-len; i++) { int j = i + len - 1; /* Sum of first and second half is same then update ans */ if (sum[i+len/2] - sum[i] == sum[i+len] - sum[i+len/2]) ans = max(ans, len); } } return ans;}// Driver program to test above functionint main(){ string str = "123123"; cout << "Length of the substring is " << findLength(str, str.length()); return 0;} |
Java
// Java implementation of O(n^2) time// and O(n) extra space solutionimport java.util.*;import java.io.*;class GFG {static int findLength(String str, int n){ // To store cumulative sum from // first digit to nth digit int sum[] = new int[ n + 1]; sum[0] = 0; /* Store cumulative sum of digits from first to last digit */ for (int i = 1; i <= n; i++) /* convert chars to int */ sum[i] = (sum[i-1] + str.charAt(i-1) - '0'); int ans = 0; // initialize result /* consider all even length substrings one by one */ for (int len = 2; len <= n; len += 2) { for (int i = 0; i <= n-len; i++) { int j = i + len - 1; /* Sum of first and second half is same then update ans */ if (sum[i+len/2] - sum[i] == sum[i+len] - sum[i+len/2]) ans = Math.max(ans, len); } } return ans;}// Driver program to test above functionpublic static void main(String[] args){ String str = "123123"; System.out.println("Length of the substring is " + findLength(str, str.length()));}}// This code is contributed by Prerna Saini |
Python3
# A O(n^2) time and O(n) extra # space solution in Python3def findLength(string, n): # To store cumulative sum # from first digit to nth digit Sum = [0] * (n + 1) # Store cumulative sum of digits # from first to last digit for i in range(1, n + 1): Sum[i] = (Sum[i - 1] + int(string[i - 1])) # convert chars to int ans = 0 # initialize result # consider all even length # substrings one by one for length in range(2, n + 1, 2): for i in range(0, n - length + 1): j = i + length - 1 # Sum of first and second half # is same then update ans if (Sum[i + length // 2] - Sum[i] == Sum[i + length] - Sum[i + length // 2]): ans = max(ans, length) return ans # Driver code if __name__ == "__main__": string = "123123" print("Length of the substring is", findLength(string, len(string))) # This code is contributed # by Rituraj Jain |
C#
// C# implementation of O(n^2) time and O(n)// extra space solutionusing System;class GFG { static int findLength(string str, int n) { // To store cumulative sum from // first digit to nth digit int []sum = new int[ n + 1]; sum[0] = 0; /* Store cumulative sum of digits from first to last digit */ for (int i = 1; i <= n; i++) /* convert chars to int */ sum[i] = (sum[i-1] + str[i-1] - '0'); int ans = 0; // initialize result /* consider all even length substrings one by one */ for (int len = 2; len <= n; len += 2) { for (int i = 0; i <= n-len; i++) { // int j = i + len - 1; /* Sum of first and second half is same then update ans */ if (sum[i+len/2] - sum[i] == sum[i+len] - sum[i+len/2]) ans = Math.Max(ans, len); } } return ans; } // Driver program to test above function public static void Main() { string str = "123123"; Console.Write("Length of the substring" + " is " + findLength(str, str.Length)); }}// This code is contributed by nitin mittal. |
PHP
<?php// A O(n^2) time and O(n) extra space solutionfunction findLength($str, $n){ $sum[$n + 1] = array(); // To store cumulative sum from // first digit to nth digit $sum[0] = 0; /* Store cumulative sum of digits from first to last digit */ for ($i = 1; $i <= $n; $i++) $sum[$i] = ($sum[$i - 1] + $str[$i - 1] - '0'); /* convert chars to int */ $ans = 0; // initialize result /* consider all even length substrings one by one */ for ($len = 2; $len <= $n; $len += 2) { for ($i = 0; $i <= $n - $len; $i++) { $j = $i + $len - 1; /* Sum of first and second half is same then update ans */ if ($sum[$i + $len / 2] - $sum[$i] == $sum[$i + $len] - $sum[$i + $len / 2]) $ans = max($ans, $len); } } return $ans;}// Driver Code$str = "123123";echo "Length of the substring is " . findLength($str, strlen($str));// This code is contributed // by Akanksha Rai?> |
Javascript
<script>// javascript implementation of O(n^2) time// and O(n) extra space solutionfunction findLength(str , n){ // To store cumulative sum from // first digit to nth digit var sum = Array.from({length: n+1}, (_, i) => 0); sum[0] = 0; /* Store cumulative sum of digits from first to last digit */ for (var i = 1; i <= n; i++) /* convert chars to var */ sum[i] = (sum[i-1] + str.charAt(i-1).charCodeAt(0) - '0'.charCodeAt(0)); var ans = 0; // initialize result /* consider all even length substrings one by one */ for (var len = 2; len <= n; len += 2) { for (i = 0; i <= n-len; i++) { var j = i + len - 1; /* Sum of first and second half is same then update ans */ if (sum[i+parseInt(len/2)] - sum[i] == sum[i+len] - sum[i+parseInt(len/2)]) ans = Math.max(ans, len); } } return ans;}// Driver program to test above functionvar str = "123123";document.write("Length of the substring is " + findLength(str, str.length));// This code is contributed by 29AjayKumar</script> |
Output
Length of the substring is 6
[A O(n2) time and O(1) extra space solution]
The idea is to consider all possible mid points (of even length substrings) and keep expanding on both sides to get and update optimal length as the sum of two sides become equal.
Below is the implementation of the above idea.
C++
// A O(n^2) time and O(1) extra space solution#include<bits/stdc++.h>using namespace std;int findLength(string str, int n){ int ans = 0; // Initialize result // Consider all possible midpoints one by one for (int i = 0; i <= n-2; i++) { /* For current midpoint 'i', keep expanding substring on both sides, if sum of both sides becomes equal update ans */ int l = i, r = i + 1; /* initialize left and right sum */ int lsum = 0, rsum = 0; /* move on both sides till indexes go out of bounds */ while (r < n && l >= 0) { lsum += str[l] - '0'; rsum += str[r] - '0'; if (lsum == rsum) ans = max(ans, r-l+1); l--; r++; } } return ans;}// Driver program to test above functionint main(){ string str = "123123"; cout << "Length of the substring is " << findLength(str, str.length()); return 0;} |
Java
// A O(n^2) time and O(1) extra space solutionimport java.util.*;import java.io.*;class GFG { static int findLength(String str, int n) { int ans = 0; // Initialize result // Consider all possible midpoints one by one for (int i = 0; i <= n - 2; i++) { /* For current midpoint 'i', keep expanding substring on both sides, if sum of both sides becomes equal update ans */ int l = i, r = i + 1; /* initialize left and right sum */ int lsum = 0, rsum = 0; /* move on both sides till indexes go out of bounds */ while (r < n && l >= 0) { lsum += str.charAt(l) - '0'; rsum += str.charAt(r) - '0'; if (lsum == rsum) { ans = Math.max(ans, r - l + 1); } l--; r++; } } return ans; }// Driver program to test above function static public void main(String[] args) { String str = "123123"; System.out.println("Length of the substring is " + findLength(str, str.length())); }}// This code is contributed by Rajput-Ji |
Python 3
# A O(n^2) time and O(n) extra # space solution def findLength(st, n): # To store cumulative total from # first digit to nth digit total = [0] * (n + 1) # Store cumulative total of digits # from first to last digit for i in range(1, n + 1): # convert chars to int total[i] = (total[i - 1] + int(st[i - 1]) - int('0')) ans = 0 # initialize result # consider all even length # substings one by one l = 2 while(l <= n): for i in range(n - l + 1): # total of first and second half # is same than update ans if (total[i + int(l / 2)] - total[i] == total[i + l] - total[i + int(l / 2)]): ans = max(ans, l) l = l + 2 return ans # Driver Codest = "123123"print("Length of the substring is", findLength(st, len(st)))# This code is contributed by ash264 |
C#
// A O(n^2) time and O(1) extra space solutionusing System;public class GFG { static int findLength(String str, int n) { int ans = 0; // Initialize result // Consider all possible midpoints one by one for (int i = 0; i <= n - 2; i++) { /* For current midpoint 'i', keep expanding substring on both sides, if sum of both sides becomes equal update ans */ int l = i, r = i + 1; /* initialize left and right sum */ int lsum = 0, rsum = 0; /* move on both sides till indexes go out of bounds */ while (r < n && l >= 0) { lsum += str[l] - '0'; rsum += str[r] - '0'; if (lsum == rsum) { ans = Math.Max(ans, r - l + 1); } l--; r++; } } return ans; } // Driver program to test above function static public void Main() { String str = "123123"; Console.Write("Length of the substring is " + findLength(str, str.Length)); }} // This code is contributed by Rajput-Ji |
PHP
<?php // A O(n^2) time and O(1) extra space solutionfunction findLength($str, $n){ $ans = 0; // Initialize result // Consider all possible midpoints one by one for ($i = 0; $i <= $n - 2; $i++) { /* For current midpoint 'i', keep expanding substring on both sides, if sum of both sides becomes equal update ans */ $l = $i; $r = $i + 1; /* initialize left and right sum */ $lsum = 0; $rsum = 0; /* move on both sides till indexes go out of bounds */ while ($r < $n && $l >= 0) { $lsum += $str[$l] - '0'; $rsum += $str[$r] - '0'; if ($lsum == $rsum) $ans = max($ans, $r - $l + 1); $l--; $r++; } } return $ans;}// Driver program to test above function$str = "123123";echo "Length of the substring is " . findLength($str, strlen($str));return 0;// This code is contributed by Ita_c.?> |
Javascript
<script>// A O(n^2) time and O(1) extra space solution function findLength(str,n) { let ans = 0; // Initialize result // Consider all possible midpoints one by one for (let i = 0; i <= n - 2; i++) { /* For current midpoint 'i', keep expanding substring on both sides, if sum of both sides becomes equal update ans */ let l = i, r = i + 1; /* initialize left and right sum */ let lsum = 0, rsum = 0; /* move on both sides till indexes go out of bounds */ while (r < n && l >= 0) { lsum += str.charAt(l) - '0'; rsum += str.charAt(r) - '0'; if (lsum == rsum) { ans = Math.max(ans, r - l + 1); } l--; r++; } } return ans; } // Driver program to test above function let str="123123"; document.write("Length of the substring is " + findLength(str, str.length)); // This code is contributed by avanitrachhadiya2155</script> |
Output
Length of the substring is 6
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
