Dada la string binaria str , la tarea es contar el número de substrings de la string dada str de modo que cada carácter de la substring pertenezca a una substring palindrómica de longitud de al menos 2.
Ejemplos:
Entrada: S = “00111”
Salida: 6
Explicación:
Hay 6 substrings de este tipo en la string dada, de modo que cada carácter pertenece a un palíndromo de tamaño mayor que 1 como {“00”, “0011”, “00111”, “11 ”, “111”, “11”}Entrada: S = “0001011”
Salida: 15
Enfoque: la idea es contar las substrings en las que cada carácter no pertenece a una substring palindrómica y luego restar este recuento del número total de posibles substrings de la string de tamaño mayor que 1. A continuación se muestra la ilustración de los pasos:
- Se puede observar que si tomamos la substring a 2 a 3 ….a k-1 (es decir, sin carácter inicial y final), entonces cada uno de sus caracteres puede pertenecer a algún palíndromo. Prueba:
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.
- Por tanto, existen cuatro patrones de substrings en los que cada carácter no pertenece al palíndromo:
- “0111….11”
- “100…..00”
- “111….110”
- “000….001”
- Finalmente, reste este recuento del número total de substrings posibles de longitud superior a 1.
Count = (N*(N – 1)/2) – (Count de las substrings en las que cada carácter no pertenece a palindrome)
A continuación se muestra la implementación del enfoque anterior:
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>
Producción:
6
Complejidad temporal: O(N)
Espacio auxiliar: O(N)