Bei einem gegebenen binären String str besteht die Aufgabe darin, die Anzahl der Teilstrings des gegebenen Strings str so zu zählen, dass jedes Zeichen des Teilstrings zu einem palindromischen Teilstring der Länge mindestens 2 gehört.
Beispiele:

Eingabe: S = „00111“ 
Ausgabe: 6 
Erläuterung: 
Es gibt 6 solcher Teilzeichenfolgen in der angegebenen Zeichenfolge, sodass jedes Zeichen zu einem Palindrom mit einer Größe größer als 1 gehört, wie {“00“, „0011“, „00111“, „11 “, „111“, „11“}
Eingabe: S = „0001011“ 
Ausgabe: 15

Ansatz: Die Idee besteht darin, die Teilzeichenfolgen zu zählen, in denen nicht jedes Zeichen zu einer palindromen Teilzeichenfolge gehört, und diese Anzahl dann von der Gesamtzahl der möglichen Teilzeichenfolgen der Zeichenfolge mit einer Größe größer als 1 zu subtrahieren. Unten ist die Illustration der Schritte:

  • Es kann beobachtet werden, dass, wenn wir den Teilstring a 2 a 3 ….a k-1 nehmen (dh ohne Anfangs- und Endzeichen), jedes seiner Zeichen zu einem Palindrom gehören kann. Nachweisen:
    Wenn a i == a i-1 oder a i == a i+1 ,
Dann gehört es zu einem Palindrom der Länge 2.

Andernfalls gilt: Wenn a i != a i-1 ,
a i != a i+1 und a i+1 == a i-1 ,
Dann gehört es zu einem Palindrom der Größe 3.
  • Daher gibt es vier Muster von Teilzeichenfolgen, in denen nicht jedes Zeichen zum Palindrom gehört: 
    1. „0111….11“
    2. „100…..00“
    3. „111….110“
    4. „000….001“
  • Subtrahieren Sie schließlich diese Anzahl von der Gesamtzahl der möglichen Teilzeichenfolgen mit einer Länge größer als 1.

    Count = (N*(N – 1)/2) – (Anzahl der Teilstrings, in denen jedes Zeichen nicht zum Palindrom gehört)

Unten ist die Implementierung des obigen Ansatzes:

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
    // continious 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     
    // continious 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     
    // continious 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     
    // continious 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>
Ausgabe: 
6

Zeitkomplexität: O(N) 
Hilfsraum: O(N)
 

Falls Sie an Live-Kursen mit Experten teilnehmen möchten , beziehen Sie sich bitte auf DSA Live-Kurse für Berufstätige und Competitive Programming Live for Students .