Given a string, the task is to find the number of such balancing positions in the string from where the left and the right part of that string contains the same characters. The frequency of characters doesn’t matter.
Examples:
Input : str[] = abaaba Output : Number of balancing positions : 3 Explanations : All 3 balancing positions are as : ab|aaba, aba|aba, abaa|ba Input : str[] = noon Output : Number of balancing positions : 1 Explanations : Balancing position is : no|on
Naive Approach:
If we try to solve this problem by the naive approach, we have to process for all n positions of string and at each position, we must check whether the left and right parts of our string from that position have the same characters or not.
The process of finding whether the position is balancing or not (frequency of both parts need not be the same) can be done in O(n^2) time for a single position( where we should check if each element in the left part is present in right and vice-versa). This whole process will lead to an algorithm of time complexity O(n^3).
Efficient Approach:
The idea of an efficient algorithm came from this article. The main difference is that we should not care about equal frequency, and using traversing the string.
We first fill right[] with counts of all characters. Then we traverse the string from left to right. For every character, we increment its count in left[] and decrement count in right[]. For any point being traversed, if all characters that have a non-zero value in left also have a non-zero value in right, and vice versa is also true, then we increment the result.
Implementation:
C++
// C++ program to find number of balancing // points in string #include<bits/stdc++.h> using namespace std; const int MAX_CHAR = 256; // function to return number of balancing points int countBalance( char *str) { int n = strlen (str); // string length // hash array for storing hash of string // initialized by 0 being global int leftVisited[MAX_CHAR] = {0}; int rightVisited[MAX_CHAR] = {0}; // process string initially for rightVisited for ( int i=0; i<n; i++) rightVisited[str[i]]++; // check for balancing points int res = 0; for ( int i=0; i<n; i++) { // for every position inc left hash // & dec rightVisited leftVisited[str[i]]++; rightVisited[str[i]]--; // check whether both hash have same // character or not int j; for (j=0; j<MAX_CHAR; j++) { // Either both leftVisited[j] and // rightVisited[j] should have none // zero value or both should have // zero value if ( (leftVisited[j] == 0 && rightVisited[j] != 0) || (leftVisited[j] != 0 && rightVisited[j] == 0) ) break ; } // if both have same character increment // count if (j == MAX_CHAR) res++; } return res; } //driver program int main() { char str[] = "abaababa" ; cout << countBalance(str); return 0; } |
Java
// Java program to find number of balancing // points in string class GFG { static final int MAX_CHAR = 256 ; // method to return number of balancing points static int countBalance(String s) { char [] str=s.toCharArray(); int n = str.length; // string length // hash array for storing hash of string // initialized by 0 being global int [] rightVisited = new int [MAX_CHAR]; int [] leftVisited = new int [MAX_CHAR]; // process string initially for rightVisited for ( int i= 0 ; i<n; i++) rightVisited[str[i]]++; // check for balancing points int res = 0 ; for ( int i= 0 ; i<n; i++) { // for every position inc left hash // & dec rightVisited leftVisited[str[i]]++; rightVisited[str[i]]--; // check whether both hash have same // character or not int j; for (j= 0 ; j<MAX_CHAR; j++) { // Either both leftVisited[j] and // rightVisited[j] should have none // zero value or both should have // zero value if ( (leftVisited[j] == 0 && rightVisited[j] != 0 ) || (leftVisited[j] != 0 && rightVisited[j] == 0 ) ) break ; } // if both have same character increment // count if (j == MAX_CHAR) res++; } return res; } // Driver Method public static void main(String[] args) { String str = "abaababa" ; System.out.println(countBalance(str)); } } /* This code is contributed by Mr. Somesh Awasthi */ |
Python3
# Python3 program to find number of # balancing points in string MAX_CHAR = 256 # function to return number of # balancing points def countBalance(string): n = len (string) # string length # hash array for storing hash of # string initialized by 0 being global leftVisited = [ 0 ] * (MAX_CHAR) rightVisited = [ 0 ] * (MAX_CHAR) # process string initially for # rightVisited for i in range ( 0 , n): rightVisited[ ord (string[i])] + = 1 # check for balancing points res = 0 for i in range ( 0 , n): # for every position inc left # hash & dec rightVisited leftVisited[ ord (string[i])] + = 1 rightVisited[ ord (string[i])] - = 1 # check whether both hash have # same character or not j = 0 while j < MAX_CHAR: # Either both leftVisited[j] and # rightVisited[j] should have none # zero value or both should have # zero value if ((leftVisited[j] = = 0 and rightVisited[j] ! = 0 ) or (leftVisited[j] ! = 0 and rightVisited[j] = = 0 )): break j + = 1 # if both have same character # increment count if j = = MAX_CHAR: res + = 1 return res # Driver Code if __name__ = = "__main__" : string = "abaababa" print (countBalance(string)) # This code is contributed # by Rituraj Jain |
C#
// C# program to find number of // balancing points in string using System; class GFG { static int MAX_CHAR = 256; // method to return number of // balancing points static int countBalance( string s) { //char[] str=s.toCharArray(); int n = s.Length; // string length // hash array for storing hash of string // initialized by 0 being global int [] rightVisited = new int [MAX_CHAR]; int [] leftVisited = new int [MAX_CHAR]; // process string initially for rightVisited for ( int i = 0; i < n; i++) rightVisited[s[i]]++; // check for balancing points int res = 0; for ( int i = 0; i < n; i++) { // for every position inc left // hash & dec rightVisited leftVisited[s[i]]++; rightVisited[s[i]]--; // check whether both hash have // same character or not int j; for (j = 0; j < MAX_CHAR; j++) { // Either both leftVisited[j] and // rightVisited[j] should have none // zero value or both should have // zero value if ((leftVisited[j] == 0 && rightVisited[j] != 0) || (leftVisited[j] != 0 && rightVisited[j] == 0)) break ; } // if both have same character // increment count if (j == MAX_CHAR) res++; } return res; } // Driver Code public static void Main(String []args) { string str = "abaababa" ; Console.WriteLine(countBalance(str)); } } // This code is contributed by vt_m. |
PHP
<?php // PHP program to find number of balancing // points in string $MAX_CHAR = 256; // function to return number of balancing points function countBalance( $str ) { global $MAX_CHAR ; $n = strlen ( $str ); // string length // hash array for storing hash of string // initialized by 0 being global $leftVisited = array_fill (0, $MAX_CHAR , NULL); $rightVisited = array_fill (0, $MAX_CHAR , NULL); // process string initially for rightVisited for ( $i = 0; $i < $n ; $i ++) $rightVisited [ord( $str [ $i ])]++; // check for balancing points $res = 0; for ( $i = 0; $i < $n ; $i ++) { // for every position inc left hash // & dec rightVisited $leftVisited [ord( $str [ $i ])]++; $rightVisited [ord( $str [ $i ])]--; // check whether both hash have same // character or not for ( $j = 0; $j < $MAX_CHAR ; $j ++) { // Either both leftVisited[j] and // rightVisited[j] should have none // zero value or both should have // zero value if (( $leftVisited [ $j ] == 0 && $rightVisited [ $j ] != 0) || ( $leftVisited [ $j ] != 0 && $rightVisited [ $j ] == 0) ) break ; } // if both have same character // increment count if ( $j == $MAX_CHAR ) $res ++; } return $res ; } // Driver Code $str = "abaababa" ; echo countBalance( $str ); // This code is contributed by Akanksha Rai ?> |
Javascript
<script> // Javascript program to find number of balancing // points in string var MAX_CHAR = 256; // function to return number of balancing points function countBalance(str) { var n = str.length; // string length // hash array for storing hash of string // initialized by 0 being global var leftVisited = Array(MAX_CHAR).fill(0); var rightVisited = Array(MAX_CHAR).fill(0); // process string initially for rightVisited for ( var i=0; i<n; i++) rightVisited[str[i].charCodeAt(0)]++; // check for balancing points var res = 0; for ( var i=0; i<n; i++) { // for every position inc left hash // & dec rightVisited leftVisited[str[i].charCodeAt(0)]++; rightVisited[str[i].charCodeAt(0)]--; // check whether both hash have same // character or not var j; for (j=0; j<MAX_CHAR; j++) { // Either both leftVisited[j] and // rightVisited[j] should have none // zero value or both should have // zero value if ( (leftVisited[j] == 0 && rightVisited[j] != 0) || (leftVisited[j] != 0 && rightVisited[j] == 0) ) break ; } // if both have same character increment // count if (j == MAX_CHAR) res++; } return res; } //driver program var str = "abaababa" ; document.write( countBalance(str)); </script> |
5
If you like neveropen and would like to contribute, you can also write an article using contribute.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!