How many times can a word be created using the input string?

Question

Here is the problem I'm trying to solve:

Write a program to perform the following operations:

• Read two inputs - a sequence of characters S & another shorter sequence Y from two separate lines of input
• S only contains lower case characters among a-z
• Calculate and print how many times the given word Y can be generated from the given sequence S
• Characters from string S can be used in order
• Each character can be used only once

Sample Input:

apqrctklatc //input

cat //the word that we need to create from input

Output:

word cat can be formed 2 times

Answer 1

Use this:

s = 'apqrctklatc'
y = 'cat'
yc = []
for i in y:
    yc.append(s.count(i))
print(min(yc))

This, according to me is the simplest solution.

Let's see how it works:

1) It loops through the second string('cat').

2)It counts how many times each letter in the string occurs in the other string, i.e. 'apqrctklatc' and makes a list.

3)It finds the minimum value of the list formed, i.e. yc.

Answer 2

You can try this :

import re 
s="apqrctklatc"
y="cat"

ylst = [x for x in y]

print(ylst)

ycount=[]
for ychar in ylst:

    count = len(re.findall(ychar, s)) 

    ycount.append(count)

print("word",y," can be formed",min(ycount),"times")  

it's working for me also you can see my output:

Answer 3

My solution is:

• Step 1: Count the number of times that each distinct characters appear in the 2nd input. Save the result to a map, called mapA, for example: a - 2 times, b - 3 times, etc...
• Step 2: Iterate through the 1st input, count the number of times that each characters in mapA appear. Save the result to a map, called mapB.
• Step 3: Initialize a variable with a high integer value (max_int is a good choice), called result. Iterate through mapA (or mapB, since both maps have the same list of keys). For each keys in mapA, calculate the floor of mapB.value/mapA.value. If it smaller than result, set result to that value.
• Step 4: Return the result, which is the result you need.

For other cases that make your result unexpected, like: 1st input and 2nd input have no common character, etc..., make sure that you have catch all of them before following those steps. Hope that you can finish it without a sample code.

Good luck.