All Tracks Algorithms String Algorithms Problem

Mancunian And Fantabulous Genes
Tag(s):

Hashing, Medium, String Algorithms

Problem
Editorial
Analytics

Mancunian is stuck in biology class again! This time, the class is learning about the DNA of googlibodies.

Googlibodies are a rare breed of chameleons found on Red Island and visible only to the most devout Manchester United supporters. Being rare, their genes are also special. Instead of the normal A,T,G,C, they can contain any of 26 possible nucleotides, each represented by a lowercase Latin letter.

Each student is given the DNA sequence of a googlibody, of length $$L$$. Genes are found as substrings in that sequence. A fantabulous gene is one that reads the same forwards and backwards. The value of a gene is defined as the product of the length of the gene with the number of distinct nucleotides present in it.

Given a parameter $$K$$, Mancunian has to find out the number of distinct fantabulous genes having value not less than $$K$$.

Input format

The first line contains two integers $$L$$ and $$K$$, denoting the length of the DNA sequence and the specified parameter respectively.
The second line contains the sequence of length $$L$$, each character of which is a lowercase Latin letter, lying between $$a$$ to $$z$$.

Output format

Print a single integer, which is the the number of fantabulous genes having a value not less than $$K$$.

Constraints

  • $$1 \le L \le 100,000$$
  • $$1 \le K \le 1,000,000,000$$
SAMPLE INPUT
9 5
abcbadayz
SAMPLE OUTPUT
3
Explanation

There are $$9$$ distinct fantabulous genes $$a$$, $$b$$, $$c$$, $$d$$, $$y$$, $$z$$, $$ada$$, $$bcb$$ and $$abcba$$, having values 1, 1, 1, 1, 1, 1, 6, 6, and 15 respectively.

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Scala 2.11.8, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

August Easy '16

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications