Count Palindromic Substrings in a Binary String
Given a binary string S i.e. which consists only of 0βs and 1βs. Calculate the number of substrings of S which are palindromes. String S contains at most two 1βs.
Examples:
Input: S = β011β
Output: 4
Explanation: β0β, β1β, β1β and β11β are the palindromic substrings.Input: S = β0β
Output: 1
Explanation: β0β is the only palindromic substring.
Approach: This can be solved with the following idea:
Using some mathematical observation can find out number of possible palindrome substring of size 2. Rest of all size, we can find out by reducing indexes from left and right side. For more clarification, see steps.
Below are the steps to solve the problem:
- Iterate in for loop from 0 to N β 1.
- Checking whether adjacent characters are equal or not and adding in the count.
- Again iterate in the loop, and look for the following conditions:
- Start reducing the index from left and if s[i β 1]== β0β, we can decrement l by 1.
- After that, iterate from right and if s[i + 1] == β0β, we can increment r by 1.
- Update ans += min(abs(l β i), abs(r β i)).
- And if S[ i β 1] == β1β, we can increment total count of palindrome by 1.
Below is the implementation of the code:
C++
// C++ code for the above approach: #include <bits/stdc++.h> #include <iostream> using namespace std; // Function to count number of plaindrome long long countPalindrome(string S) { // Size of string int N = S.size(); long long ans = 0, x = 0; for ( int i = 0; i < N; i++) { x++; // If adjacent character are same if (i + 1 < N && S[i] == S[i + 1]) continue ; // Count total number of possibility ans += (x * (x + 1)) / 2; x = 0; } int last = -1; for ( int i = 0; i < N; i++) { if (S[i] == '1' ) { int l = i; int r = i; // Start iterating from right side while (l - 1 >= 0 && S[l - 1] == '0' ) l--; // Start iterating from left side while (r + 1 < N && S[r + 1] == '0' ) r++; ans += min( abs (l - i), abs (r - i)); if (last == -1) { last = i; } else { // Add the min value ans += min(last, N - i - 1); if (S[i - 1] != '1' ) { ans++; } } } } // Return the total count of // palindromic substrings return ans; } // Driver code int main() { string s = "01110" ; // Function call cout << countPalindrome(s); return 0; } |
Java
// Code contributed by Flutterfly import java.util.*; class Main { public static long countPalindrome(String S) { // Size of string int N = S.length(); long ans = 0 , x = 0 ; for ( int i = 0 ; i < N; i++) { x++; // If adjacent character are same if (i + 1 < N && S.charAt(i) == S.charAt(i + 1 )) continue ; // Count total number of possibility ans += (x * (x + 1 )) / 2 ; x = 0 ; } int last = - 1 ; for ( int i = 0 ; i < N; i++) { if (S.charAt(i) == '1' ) { int l = i; int r = i; // Start iterating from right side while (l - 1 >= 0 && S.charAt(l - 1 ) == '0' ) l--; // Start iterating from left side while (r + 1 < N && S.charAt(r + 1 ) == '0' ) r++; ans += Math.min(Math.abs(l - i), Math.abs(r - i)); if (last == - 1 ) { last = i; } else { // Add the min value ans += Math.min(last, N - i - 1 ); if (S.charAt(i - 1 ) != '1' ) { ans++; } } } } // Return the total count of // palindromic substrings return ans; } // Driver code public static void main(String[] args) { String s = "01110" ; //Function call System.out.println(countPalindrome(s)); } } |
Python
# code contributed by Flutterfly # Function to count number of palindrome def countPalindrome(S): #Size of string N = len (S) ans = 0 x = 0 for i in range (N): x + = 1 #If adjacent character are same if i + 1 < N and S[i] = = S[i + 1 ]: continue #Count total number of possibility ans + = (x * (x + 1 )) / / 2 x = 0 last = - 1 for i in range (N): if S[i] = = '1' : l = i r = i #Start iterating from right side while l - 1 > = 0 and S[l - 1 ] = = '0' : l - = 1 #Start iterating from left side while r + 1 < N and S[r + 1 ] = = '0' : r + = 1 ans + = min ( abs (l - i), abs (r - i)) if last = = - 1 : last = i else : #Add the min value ans + = min (last, N - i - 1 ) if S[i - 1 ] ! = '1' : ans + = 1 #Return the total count of palindromic substrings return ans #Driver code s = "01110" #Function call print (countPalindrome(s)) |
C#
// Code contributed by Flutterfly using System; public class Program { // Function to count number of plaindrome public static long CountPalindrome( string S) { // Size of string int N = S.Length; long ans = 0, x = 0; for ( int i = 0; i < N; i++) { x++; // If adjacent character are same if (i + 1 < N && S[i] == S[i + 1]) continue ; // Count total number of possibility ans += (x * (x + 1)) / 2; x = 0; } int last = -1; for ( int i = 0; i < N; i++) { if (S[i] == '1' ) { int l = i; int r = i; // Start iterating from right side while (l - 1 >= 0 && S[l - 1] == '0' ) l--; // Start iterating from left side while (r + 1 < N && S[r + 1] == '0' ) r++; ans += Math.Min(Math.Abs(l - i), Math.Abs(r - i)); if (last == -1) { last = i; } else { // Add the min value ans += Math.Min(last, N - i - 1); if (S[i - 1] != '1' ) { ans++; } } } } // Return the total count of // palindromic substrings return ans; } //Driver code public static void Main() { string s = "01110" ; // Function call Console.WriteLine(CountPalindrome(s)); } } |
Javascript
// JavaScript code for the above approach: // Function to count number of plaindrome function countPalindrome(S) { // Size of string const N = S.length; let ans = 0; let x = 0; for (let i = 0; i < N; i++) { x++; // If adjacent character are same if (i + 1 < N && S[i] === S[i + 1]) continue ; // Count total number of possibility ans += (x * (x + 1)) / 2; x = 0; } let last = -1; for (let i = 0; i < N; i++) { if (S[i] === '1' ) { let l = i; let r = i; // Start iterating from right side while (l - 1 >= 0 && S[l - 1] === '0' ) l--; // Start iterating from left side while (r + 1 < N && S[r + 1] === '0' ) r++; ans += Math.min(Math.abs(l - i), Math.abs(r - i)); if (last === -1) { last = i; } else { // Add the min value ans += Math.min(last, N - i - 1); if (S[i - 1] !== '1' ) { ans++; } } } } // Return the total count of // palindromic substrings return ans; } // Driver code const S = "01110" ; // Function call console.log(countPalindrome(S)); |
10
Time Complexity: O(N)
Auxiliary Space: O(1)
Contact Us