Count substring of Binary string such that each character belongs to a palindrome of size greater than 1
Given binary string str, the task is to count the number of substrings of the given string str such that each character of the substring belongs to a palindromic substring of length at least 2.
Examples:
Input: S = β00111β
Output: 6
Explanation:
There are 6 such substrings in the given string such that each character belongs to a palindrome of size greater than 1 as {β00β, β0011β, β00111β, β11β, β111β, β11β}Input: S = β0001011β
Output: 15
Approach: The idea is to count the substrings in which every character doesnβt belong to a palindromic substring and then subtract this count from the total number of possible substrings of the string of size greater than 1. Below is the illustration of the steps:
- It can be observed that if we take the substring a2a3β¦.ak-1 (i.e. without starting and ending character), then each of its characters may belong to some palindrome.Proof:
If ai == ai-1 or ai == ai+1, Then it belongs to a palindrome of length 2. Otherwise, If ai != ai-1, ai != ai+1 and ai+1 == ai-1, Then, It belongs to a palindrome of size 3.
- Therefore, there are four patterns of substrings in which each character doesnβt belong to the palindrome:
- β0111β¦.11β
- β100β¦..00β
- β111β¦.110β
- β000β¦.001β
- Finally, subtract this count from the total number of substrings possible of length greater than 1.
Count = (N*(N β 1)/2) β (Count of the substrings in which each character doesnβt belongs to palindrome)
Below is the implementation of the above approach:
C++
// C++ implementation to find the // substrings in binary string // such that every character // belongs to a palindrome #include <bits/stdc++.h> using namespace std; // Function to to find the // substrings in binary string // such that every character // belongs to a palindrome int countSubstrings(string s) { int n = s.length(); // Total substrings int answer = (n * (n - 1)) / 2; int cnt = 1; vector< int > v; // Loop to store the count of // continuous characters in // the given string for ( int i = 1; i < n; i++) { if (s[i] == s[i - 1]) cnt++; else { v.push_back(cnt); cnt = 1; } } if (cnt > 0) v.push_back(cnt); // Subtract non special // strings from answer for ( int i = 0; i < v.size() - 1; i++) { answer -= (v[i] + v[i + 1] - 1); } return answer; } // Driver Code int main() { // Given string s string s = "00111" ; // Function Call cout << countSubstrings(s); return 0; } |
Java
// Java implementation to find the // substrings in binary string // such that every character // belongs to a palindrome import java.util.*; class GFG{ // Function to to find the // substrings in binary string // such that every character // belongs to a palindrome public static int countSubstrings(String s) { int n = s.length(); // Total substrings int answer = (n * (n - 1 )) / 2 ; int cnt = 1 ; Vector<Integer> v = new Vector<Integer>(); // Loop to store the count of // continuous characters in // the given string for ( int i = 1 ; i < n; i++) { if (s.charAt(i) == s.charAt(i - 1 )) cnt++; else { v.add(cnt); cnt = 1 ; } } if (cnt > 0 ) v.add(cnt); // Subtract non special // strings from answer for ( int i = 0 ; i < v.size() - 1 ; i++) { answer -= (v.get(i) + v.get(i + 1 ) - 1 ); } return answer; } // Driver code public static void main(String[] args) { // Given string s String s = "00111" ; // Function call System.out.print(countSubstrings(s)); } } // This code is contributed by divyeshrabadiya07 |
Python3
# Python3 implementation to find the # substrings in binary string # such that every character # belongs to a palindrome # Function to find the substrings in # binary string such that every # character belongs to a palindrome def countSubstrings (s): n = len (s) # Total substrings answer = (n * (n - 1 )) / / 2 cnt = 1 v = [] # Loop to store the count # of continuous characters # in the given string for i in range ( 1 , n): if (s[i] = = s[i - 1 ]): cnt + = 1 else : v.append(cnt) cnt = 1 if (cnt > 0 ): v.append(cnt) # Subtract non special strings # from answer for i in range ( len (v) - 1 ): answer - = (v[i] + v[i + 1 ] - 1 ) return answer # Driver Code if __name__ = = '__main__' : # Given string s = "00111" # Function call print (countSubstrings(s)) # This code is contributed by himanshu77 |
C#
// C# implementation to find the // substrings in binary string // such that every character // belongs to a palindrome using System; using System.Collections.Generic; class GFG{ // Function to to find the // substrings in binary string // such that every character // belongs to a palindrome public static int countSubstrings(String s) { int n = s.Length; // Total substrings int answer = (n * (n - 1)) / 2; int cnt = 1; List< int > v = new List< int >(); // Loop to store the count of // continuous characters in // the given string for ( int i = 1; i < n; i++) { if (s[i] == s[i-1]) cnt++; else { v.Add(cnt); cnt = 1; } } if (cnt > 0) v.Add(cnt); // Subtract non special // strings from answer for ( int i = 0; i < v.Count - 1; i++) { answer -= (v[i] + v[i + 1] - 1); } return answer; } // Driver code public static void Main(String[] args) { // Given string s String s = "00111" ; // Function call Console.Write(countSubstrings(s)); } } // This code contributed by sapnasingh4991 |
Javascript
<script> // Javascript implementation to find the // substrings in binary string // such that every character // belongs to a palindrome // Function to to find the // substrings in binary string // such that every character // belongs to a palindrome function countSubstrings(s) { var n = s.length; // Total substrings var answer = (n * (n - 1)) / 2; var cnt = 1; var v =[]; // Loop to store the count of // continuous characters in // the given string for ( var i = 1; i < n; i++) { if (s.charAt(i) == s.charAt(i - 1)) cnt++; else { v.push(cnt); cnt = 1; } } if (cnt > 0) v.push(cnt); // Subtract non special // strings from answer for ( var i = 0; i < v.length - 1; i++) { answer -= (v[i] + v[i + 1] - 1); } return answer; } // Driver code //Given string s var s = "00111" ; // Function call document.write(countSubstrings(s)); // This code contributed by shikhasingrajput </script> |
6
Time Complexity: O(N)
Auxiliary Space: O(N)