SOLVE THIS PROBLEM

general
1

Ramesh really likes soup, especially when it contains alphabet pasta. Every day he constructs a sentence from letters, places the letters into a bowl of broth and enjoys delicious alphabet soup.

Today, after constructing the sentence, Alfredo remembered that the Cricket World Cup starts today! Thus, he decided to construct the phrase “WORLDCUP”. As he already added the letters to the broth, he is stuck with the letters he originally selected. Help Ramesh determine how many times he can place the word “WORLDCUP” side-by-side using the letters in his soup.

Input

The first line of the input file contains a single integer T: the number of test cases. T lines follow, each representing a single test case with a sequence of upper-case letters and spaces: the original sentence Ramesh constructed.

Output

Output T lines, one for each test case. For each case, output “Case #t: n”, where t is the test case number (starting from 1) and n is the number of times the word “WORLDCUP” can be placed side-by-side using the letters from the sentence.

Constraints

1 < T ≤ 20

Sentences contain only the upper-case letters A-Z and the space character

Each sentence contains at least one letter, and contains at most 1000 characters, including spaces

Example Input:

5

WELCOME TO CRICKET WORLDCUP

CUP WITH LABEL WORLCUP BELONGS TO WORLD

QUICK CUTE BROWN FOX JUMPS OVER THE LAZY DOG

MOVE FAST BE BOLD

WORL THE WORLDCUP

Example Output:

Case #1: 1

Case #2: 2

Case #3: 1

Case #4: 0

Case #5: 1

2

you can use hashing to solve this problem.

  • First scan the string
  • Traverse the string until you reach end of string
  • When ever you encounter ‘W’ or ‘O’ or ‘R’ or ‘L’ or ‘D’ or ‘C’ or ‘U’ or ‘P’ while traversing just increment the encountered value.
  • Eg: if hash[‘W’]=5 and if again you encounter ‘W’ then do hash[‘W’]++ so that hash[‘W’]=6 now.
  • Then after traversing the whole string take the minimum hash value among ‘W’,‘O’,‘R’,…
  • because if you have 5-'W’s 5-‘O’ 5-‘R’… and only 4-‘P’ then you can construct only 4-WORLDCUP words, that is min{hash[‘W’],hash[‘O’],hash[‘R’],hash[‘L’],…}
  • I hope you will understand this, In case any doubts comment below :slight_smile:
1 Like