INSQ16B - Editorial

PROBLEM LINK:

Contest

Practice

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

SOLUTION:

Setter’s Solution