PROBLEM LINK:
Author: Vimarsh Bhargava
Tester: Shubham Gupta
Editorialist: Vimarsh Bhargava
DIFFICULTY:
EASY
PREREQUISITES:
None
PROBLEM:
Given a string, output the number of subsquences of the string, such that all subsequences of that particular subsequence are palindromes
EXPLANATION:
First, for any string to have all of its subsequences as palindromes, it should consist of only one character. So, we have to calculate such strings which are subsequences of the original string and consist of only a single character.
Now such a string can be formed with any of the 26 letters by choosing any number of occurances of that character. So, for every occurance of a character, it can either be included in that substring or not. So if there are cnt(x) occurances of character x, then number of subsequences will be power(2,cnt(x)) - 1.(We do not consider empty subsequences.)
Therefore, answer will be (sum(power(2,cnt(x))-1) for x = ‘a’ to ‘z’) mod 1000000007