Given string str, the task is to count all the sub-strings of str which are palindromes and their length is prime.
Examples:
Input: str = “neveropen”
Output: 2
“ee” and “ee” are the only valid sub-strings.Input: str = “abccc”
Output: 3
Approach: Using Sieve of Eratosthenes, find all the primes till the length of str because that is the maximum length a sub-string of str can have. Now starting from the smallest prime i.e. j = 2 till j ? len(str). If j is prime then count all the palindromic sub-strings of str whose length = j. Print the total count at the end.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function that returns true if sub-string// starting at i and ending at j in str is a palindromebool isPalindrome(string str, int i, int j){ while (i < j) { if (str[i] != str[j]) return false; i++; j--; } return true;}// Function to count all palindromic substring// whose length is a prime numberint countPrimePalindrome(string str, int len){ bool prime[len + 1]; memset(prime, true, sizeof(prime)); // 0 and 1 are non-primes prime[0] = prime[1] = false; for (int p = 2; p * p <= len; p++) { // If prime[p] is not changed, then it is a prime if (prime[p]) { // Update all multiples of p greater than or // equal to the square of it // numbers which are multiple of p and are // less than p^2 are already been marked. for (int i = p * p; i <= len; i += p) prime[i] = false; } } // To store the required number of sub-strings int count = 0; // Starting from the smallest prime till // the largest length of the sub-string possible for (int j = 2; j <= len; j++) { // If j is prime if (prime[j]) { // Check all the sub-strings of length j for (int i = 0; i + j - 1 < len; i++) { // If current sub-string is a palindrome if (isPalindrome(str, i, i + j - 1)) count++; } } } return count;}// Driver Codeint main(){ string s = "neveropen"; int len = s.length(); cout << countPrimePalindrome(s, len); return 0;} |
Java
// Java implementation of the approach import java.util.Arrays;class GfG{ // Function that returns true if // sub-string starting at i and // ending at j in str is a palindrome static boolean isPalindrome(String str, int i, int j) { while (i < j) { if (str.charAt(i) != str.charAt(j)) return false; i++; j--; } return true; } // Function to count all palindromic substring // whose length is a prime number static int countPrimePalindrome(String str, int len) { boolean[] prime = new boolean[len + 1]; Arrays.fill(prime, true); // 0 and 1 are non-primes prime[0] = prime[1] = false; for (int p = 2; p * p <= len; p++) { // If prime[p] is not changed, // then it is a prime if (prime[p]) { // Update all multiples of p greater than or // equal to the square of it // numbers which are multiple of p and are // less than p^2 are already been marked. for (int i = p * p; i <= len; i += p) prime[i] = false; } } // To store the required number of sub-strings int count = 0; // Starting from the smallest prime till // the largest length of the sub-string possible for (int j = 2; j <= len; j++) { // If j is prime if (prime[j]) { // Check all the sub-strings of length j for (int i = 0; i + j - 1 < len; i++) { // If current sub-string is a palindrome if (isPalindrome(str, i, i + j - 1)) count++; } } } return count; } // Driver code public static void main(String []args) { String s = "neveropen"; int len = s.length(); System.out.println(countPrimePalindrome(s, len)); }}// This code is contributed by Rituraj Jain |
Python3
# Python3 implementation of the approachimport math as mt# Function that returns True if sub-string# starting at i and ending at j in str1 # is a palindromedef isPalindrome(str1, i, j): while (i < j): if (str1[i] != str1[j]): return False i += 1 j -= 1 return True # Function to count all palindromic substring# whose length is a prime numberdef countPrimePalindrome(str1, Len): prime = [True for i in range(Len + 1)] # 0 and 1 are non-primes prime[0], prime[1] = False, False for p in range(2, mt.ceil(mt.sqrt(Len + 1))): # If prime[p] is not changed, # then it is a prime if (prime[p]): # Update all multiples of p greater # than or equal to the square of it # numbers which are multiple of p # and are less than p^2 are already # been marked. for i in range(2 * p, Len + 1, p): prime[i] = False # To store the required number # of sub-strings count = 0 # Starting from the smallest prime # till the largest Length of the # sub-string possible for j in range(2, Len + 1): # If j is prime if (prime[j]): # Check all the sub-strings of # Length j for i in range(Len + 1 - j): # If current sub-string is a palindrome if (isPalindrome(str1, i, i + j - 1)): count += 1 return count# Driver Codes = "neveropen"Len = len(s)print( countPrimePalindrome(s, Len))# This code is contributed by # Mohit kumar 29 |
C#
// C# implementation of the approach using System;class GfG{// Function that returns true if // sub-string starting at i and // ending at j in str is a palindrome static bool isPalindrome(string str, int i, int j) { while (i < j) { if (str[i] != str[j]) return false; i++; j--; } return true; } // Function to count all palindromic // substring whose length is a prime number static int countPrimePalindrome(string str, int len) { bool[] prime = new bool[len + 1]; Array.Fill(prime, true); // 0 and 1 are non-primes prime[0] = prime[1] = false; for (int p = 2; p * p <= len; p++) { // If prime[p] is not changed, // then it is a prime if (prime[p]) { // Update all multiples of p greater // than or equal to the square of it // numbers which are multiple of p // and are less than p^2 are already // been marked. for (int i = p * p; i <= len; i += p) prime[i] = false; } } // To store the required number // of sub-strings int count = 0; // Starting from the smallest prime // till the largest length of the // sub-string possible for (int j = 2; j <= len; j++) { // If j is prime if (prime[j]) { // Check all the sub-strings of // length j for (int i = 0; i + j - 1 < len; i++) { // If current sub-string is a // palindrome if (isPalindrome(str, i, i + j - 1)) count++; } } } return count; } // Driver codepublic static void Main(){ string s = "neveropen"; int len = s.Length; Console.WriteLine(countPrimePalindrome(s, len));}}// This code is contributed by Code_Mech |
Javascript
<script>// Javascript implementation of the approach// Function that returns true if sub-string// starting at i and ending at j in str is a palindromefunction isPalindrome(str, i, j){ while (i < j) { if (str[i] != str[j]) return false; i++; j--; } return true;}// Function to count all palindromic substring// whose length is a prime numberfunction countPrimePalindrome(str, len){ var prime = Array(len + 1).fill(true); // 0 and 1 are non-primes prime[0] = prime[1] = false; for (var p = 2; p * p <= len; p++) { // If prime[p] is not changed, then it is a prime if (prime[p]) { // Update all multiples of p greater than or // equal to the square of it // numbers which are multiple of p and are // less than p^2 are already been marked. for (var i = p * p; i <= len; i += p) prime[i] = false; } } // To store the required number of sub-strings var count = 0; // Starting from the smallest prime till // the largest length of the sub-string possible for (var j = 2; j <= len; j++) { // If j is prime if (prime[j]) { // Check all the sub-strings of length j for (var i = 0; i + j - 1 < len; i++) { // If current sub-string is a palindrome if (isPalindrome(str, i, i + j - 1)) count++; } } } return count;}// Driver Codevar s = "neveropen";var len = s.length;document.write( countPrimePalindrome(s, len));</script> |
PHP
<?php// PHP implementation of the approach // Function that returns true if sub-string // starting at i and ending at j in str is // a palindrome function isPalindrome($str, $i, $j) { while ($i < $j) { if ($str[$i] != $str[$j]) return false; $i++; $j--; } return true; } // Function to count all palindromic substring // whose length is a prime number function countPrimePalindrome($str, $len) { $prime = array_fill(0, $len + 1, true); // 0 and 1 are non-primes $prime[0] = false ; $prime[1] = false; for ($p = 2; $p * $p <= $len; $p++) { // If prime[p] is not changed, // then it is a prime if ($prime[$p]) { // Update all multiples of p greater // than or equal to the square of it // numbers which are multiple of p and are // less than p^2 are already been marked. for ($i = $p * $p; $i <= $len; $i += $p) $prime[$i] = false; } } // To store the required number // of sub-strings $count = 0; // Starting from the smallest prime till // the largest length of the sub-string possible for ($j = 2; $j <= $len; $j++) { // If j is prime if ($prime[$j]) { // Check all the sub-strings of length j for ($i = 0; $i + $j - 1 < $len; $i++) { // If current sub-string is a palindrome if (isPalindrome($str, $i, $i + $j - 1)) $count++; } } } return $count; } // Driver Code $s = "neveropen"; $len = strlen($s); echo countPrimePalindrome($s, $len); // This code is contributed by Ryuga?> |
Output:
2
Python program to count all prime length palindromic substrings :
Approach steps:
1.Define a function count_palindromic_substrings that takes a string s as input. The function will return the count of all prime length palindromic substrings in s.
2.Define a helper function is_palindrome that takes a string s as input and returns True if s is a palindrome, and False otherwise. This function checks if the string is equal to its reverse.
3.Initialize a variable count to 0 to keep track of the total count of prime length palindromic substrings.
4.Iterate over all possible substring lengths p from 2 to n (length of s), and check if p is a prime number using a loop that runs from 2 to the square root of p. If p is a prime number, iterate over all substrings of length p and check if each substring is a palindrome using the is_palindrome helper function. If the substring is a palindrome, increment the count variable.
5.Return the total count of prime length palindromic substrings.
6.In the example usage, create a string s and call the count_palindromic_substrings function with this argument. Finally, print the total count of prime length palindromic substrings.
C++
#include <iostream>#include <string>#include <cmath>using namespace std;// helper function to check if a string is a palindromebool is_palindrome(string s) { return s == string(s.rbegin(), s.rend());}int count_palindromic_substrings(string s) { int count = 0; int n = s.length(); // iterate over all possible substrings of length `p` for (int p = 2; p <= n; p++) { // check if `p` is a prime number bool is_prime = true; for (int i = 2; i <= sqrt(p); i++) { if (p % i == 0) { is_prime = false; break; } } if (is_prime) { // iterate over all substrings of length `p` for (int i = 0; i <= n - p; i++) { if (is_palindrome(s.substr(i, p))) { count++; } } } } // return the total count of prime length palindromic substrings return count;}int main() { string s = "abccba"; int count = count_palindromic_substrings(s); cout << "Total number of prime length palindromic substrings in " << s << " is " << count << endl; return 0;} |
Java
import java.util.*;public class Main { // helper function to check if a string is a palindrome public static boolean isPalindrome(String s) { return s.equals(new StringBuilder(s).reverse().toString()); } public static int countPalindromicSubstrings(String s) { int count = 0; int n = s.length(); // iterate over all possible substrings of length `p` for (int p = 2; p <= n; p++) { // check if `p` is a prime number boolean isPrime = true; for (int i = 2; i <= Math.sqrt(p); i++) { if (p % i == 0) { isPrime = false; break; } } if (isPrime) { // iterate over all substrings of length `p` for (int i = 0; i <= n - p; i++) { if (isPalindrome(s.substring(i, i + p))) { count++; } } } } // return the total count of prime length palindromic substrings return count; } public static void main(String[] args) { String s = "abccba"; int count = countPalindromicSubstrings(s); System.out.println("Total number of prime length palindromic substrings in " + s + " is " + count); }} |
Python3
# program to count all prime length palindromic substrings in a given stringdef count_palindromic_substrings(s): # helper function to check if a string is a palindrome def is_palindrome(s): return s == s[::-1] count = 0 n = len(s) # iterate over all possible substrings of length `p` for p in range(2, n+1): # check if `p` is a prime number is_prime = True for i in range(2, int(p**0.5)+1): if p % i == 0: is_prime = False break if is_prime: # iterate over all substrings of length `p` for i in range(n-p+1): if is_palindrome(s[i:i+p]): count += 1 # return the total count of prime length palindromic substrings return count# example usages = "abccba"count = count_palindromic_substrings(s)print("Total number of prime length palindromic substrings in", s, "is", count) |
Javascript
function count_palindromic_substrings(s) { // helper function to check if a string is a palindrome function is_palindrome(s) { return s === s.split("").reverse().join(""); } let count = 0; const n = s.length; // iterate over all possible substrings of length `p` for (let p = 2; p <= n; p++) { // check if `p` is a prime number let is_prime = true; for (let i = 2; i <= Math.floor(Math.sqrt(p)); i++) { if (p % i === 0) { is_prime = false; break; } } if (is_prime) { // iterate over all substrings of length `p` for (let i = 0; i <= n-p; i++) { if (is_palindrome(s.substring(i, i+p))) { count += 1; } } } } // return the total count of prime length palindromic substrings return count;}// example usageconst s = "abccba";const count = count_palindromic_substrings(s);console.log(`Total number of prime length palindromic substrings in ${s} is ${count}`); |
C#
using System;class MainClass { // helper function to check if a string is a palindrome public static bool isPalindrome(string s) { char[] charArray = s.ToCharArray(); Array.Reverse(charArray); return s == new string(charArray); } public static int countPalindromicSubstrings(string s) { int count = 0; int n = s.Length; // iterate over all possible substrings of length `p` for (int p = 2; p <= n; p++) { // check if `p` is a prime number bool isPrime = true; for (int i = 2; i <= Math.Sqrt(p); i++) { if (p % i == 0) { isPrime = false; break; } } if (isPrime) { // iterate over all substrings of length `p` for (int i = 0; i <= n - p; i++) { if (isPalindrome(s.Substring(i, p))) { count++; } } } } // return the total count of prime length palindromic substrings return count; } public static void Main (string[] args) { string s = "abccba"; int count = countPalindromicSubstrings(s); Console.WriteLine("Total number of prime length palindromic substrings in " + s + " is " + count); }} |
Output
Total number of prime length palindromic substrings in abccba is 1
Time complexity: O(n^2 log n)
Auxiliary Space: O(1).
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
