How to Solve “stringsConstruction” in CodeFights

The Problem:

How many strings equal to A can be constructed using letters from the string B? Each letter can be used only once and in one string only.

Example

For A = "abc" and B = "abccba", the output should be
stringsConstruction(A, B) = 2.

We can construct 2 strings A with letters from B.

Input/Output

  • [time limit] 4000ms (py)
  • [input] string A

    String to construct, A contains only lowercase English letters.

    Constraints:
    3 ≤ A.length ≤ 10.

  • [input] string B

    String containing needed letters, B contains only lowercase English letters.

    Constraints:
    3 ≤ B.length ≤ 50.

  • [output] integer

The Solution:
def stringsConstruction(A, B):
dA = {}
dB={}
for x in A:
dA[x]=dA.get(x,0)+1
for x in B:
dB[x]=dB.get(x,0)+1
minn = 9999
for x in A:
r = dB.get(x,0)/dA[x]
if r<minn:
minn=r
return minn

The Explanation:

My way of solving is to use dictionaries, although we could easily do it with an array, too. The purpose of dictionaries is to keep track of the letters in the strings, “How many times letter ‘c’ is seen in string A?”, etc.

And, the algorithm is to find the minimum multiple of the letters found in the string.
To be clear,
We count the number of times it is repeated for each letter. Let’s say we saw 2 b’s and 3 a’s in string A. and 3 b’s and 9 a’s in string B.
This means that we can create 3 times the a’s in string A and once only the b’s in string A. At the end, we can create string A one time only because we run out of letter b.
If we had A = “aabbc” and B = “aaaabbbbccc” we would have the answer 2.
The answer we get would be 2. Because, we can get letter a two times and letter b two times and letter c 3 times. The minimum of these is 2 times.
FYI, the get function of dictionary gets the requested key. And, if it is not found, it creates the key and sets the default value as the second parameter.
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s