All Tracks Algorithms Searching Binary Search Problem

Candies
Tag(s):

Algorithms, Binary Search, Easy, Searching, String Searching, Two-pointer

Problem
Editorial
Analytics

You are given a string S consisting of lowercase English letters denoting different types of candies. A substring of a string S is a string S' that occurs in S. For example, "bam" is a substring of "babammm". Each candy costs 1 unit. You can pick some continuous candies such that you can create a palindrome of length K by using some or all picked candies. Your task is to find the minimum cost to create a palindrome of length K.

 

Input Format:

First line contains string S.

Next line contains an integer T denoting the number of test cases.

Next T lines contain a single integer K.

 

Output Format:

For each test case, print minimum cost as mentioned above. If you cannot create a palindrome of length K then, simply print -1.

 

Constraints:

\(1 \le |S| \le 10^5\\ 1\le T \le 10\\ 1\le K \le 10^5\)

SAMPLE INPUT
babammm
2
2
5
SAMPLE OUTPUT
2
5
Explanation

Test Case 1: You can pick candies denoted by "mm" and create a palindrome of size 2. So the cost will be 2 units.

Test Case 2: You can pick candies denoted by "babam" and rearrange them, "bamab", to create a palindrome of size 5. So the cost will be 5 units.

Time Limit: 1.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: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

MakeMyTrip

Challenge Name

MakeMyTrip Java Developer Hiring Challenge

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?