SubStrings & Collections

SubStrings & Collections

Today, we are going to solve a problem related to SubStrings & Collections.
For problem definition, visit below hackerrank web page ( copied & pasted below for easy reference).


https://www.hackerrank.com/contests/hourrank-30/challenges/video-conference/problem

** Courtesy : HackerRank

Bob is making a video conference software. Whenever a new person joins the conference, Bob displays the person's name in the interface.

However, displaying full name is tedious and takes much space. So he decided to display the shortest prefix which doesn't match with any prefix of any person who has joined earlier.

Let's suppose the first person to enter the conference is alvin.

Now suppose next person to join is alice. The shortest prefix of alice that doesn't match with any prefix of alvin is ali.

If the full name of a new person matches completely with the full name of any person who has joined earlier, he will display the full name and add a suffix which indicates how many times the same name has occurred in the list so far. For example, if another person name alvin joins, the list will look like this:

You are given the list of the persons who have joined the call in the chronological order. Your task is to figure out how the final list looks like.

Input Format

The first line contains an integer .

The subsequent  line contains a string  denoting the name of the  person to join the call.

Constraints

•  will contain only lower-case english letters.

Output Format

Return a string array with  items, the  line should contain the prefix of name of the person which doesn't match with any other person who has joined earlier.

Sample Input 0

3
alvin
alice
alvin

Sample Output 0

a
ali
alvin 2

Sample Input 1

6
mary
stacy
sam
samuel
sam
miguel

Sample Output 1

m
s
sa
samu
sam 2
mi

Solution :

Looking at the problem definition, here is what you need :

1> Since you need to make sure that person with same name joins the conference , he would be tagged as name +<<count>> ( name2 , name3 etc) , we need a map of <String,Integer> which will store person names and count.Let's call this as UsedMainStrings Map.

For every person name, you will first search inside this Map and if the occurrence is found , you will increment the count and add it to result ( name 2 or name 3 etc).

If no occurrence is found, we need to go to #2 to do subStringing()

Peek at Code :
Note : First Person name handling is also included here, it would be very easy to handle the first person. Just use the character at 0th place:

List<String> result = new ArrayList<String>(); Map<String, Integer> usedMainStrings = new HashMap<String, Integer>(); result.add(names.get(0).substring(0, 1)); addUsedMainString(usedMainStrings, names.get(0)); addUsedSubStrings(usedSubStrings, names.get(0)); for (int i = 1; i < names.size(); i++) { String next = names.get(i); Integer occurence = usedMainStrings.get(next); if (occurence != null && occurence > 0) { occurence++; result.add(next + " " + occurence); }

Implementation of addUsedMainString :

private static void addUsedMainString(Map<String, Integer> usedMainStrings, String string) {
usedMainStrings.put(string, getOccurence(usedMainStrings, string)); }

private static int getOccurence(Map<String, Integer> stringMap, String string) {
return stringMap.get(string) == null ? 1 : stringMap.get(string) + 1;
} 

2> Looking at problem again, you will start subStringing the person name starting with 0 to 0 , 0 to 1, 0 to 2 and so on till 0 to n-2 where n is length of String ( person name)

Why on Earth n-2? Its because , o to n-1 is full String which are going to first scan for occurence before going for subStringing

To achieve this SubStringing with good performance , again have a Map but this time as Map of <String, String> as we dont need to track count of subStrings rather if match is found , we move to next subString.Let's call this as UsedSubStrings Map.

In this map , we will store subString ( explained above , 0 to 0 .... o to n-1) as KEY and value would be a dummy value "I am available".

Important:Did you notice? When storing subStrings , we store from 0 to 0, ... o to n-1 while when searching for subString we only search a substring of a person from 0 to 0 ..o to n-2 ..

In former case ,we store all because this itself could be a subString for any other person name . for example, sam is person name while it is subString of Samuel . So if these two person join the call , they would be tagged as S and Samu that's why we need whole person name in subString Map.

As far as , searching goes , we have already searched for whole person name in UsedMainStrings Map and we know there is no person with Name and that's why we are here at #2.

So if person name is not found in #1 , go for SubStrining your person name and use that subString which is not found inside this UsedSubStrings Map.

Peek at code :

List<String> result = new ArrayList<String>(); Map<String, Integer> usedMainStrings = new HashMap<String, Integer>(); Map<String, String> usedSubStrings = new HashMap<String, String>(); result.add(names.get(0).substring(0, 1)); addUsedMainString(usedMainStrings, names.get(0)); addUsedSubStrings(usedSubStrings, names.get(0)); for (int i = 1; i < names.size(); i++) { String next = names.get(i); Integer occurence = usedMainStrings.get(next); if (occurence != null && occurence > 0) { occurence++; result.add(next + " " + occurence); } else { for (int j = 1; j <= next.length(); j++) { String nextSubString = next.substring(0, j); if(!usedSubStrings.containsKey(nextSubString)) { result.add(nextSubString); break; } } } addUsedMainString(usedMainStrings, next); addUsedSubStrings(usedSubStrings, next); } return result;

Implementation of addUsedSubString :

private static void addUsedSubStrings(Map<String, String> usedStrings, String string) { for (int i = 1; i <= string.length(); i++) { String subStr = string.substring(0, i); usedStrings.put(subStr, "I am available here"); } }

3> This is important step or logic. You may miss this ( even I missed :( ) . You may say that we are done , but were are not.

There might be a case , where next person name is not foun in UsedMainStrings Map in #1 above and you were not able to find any unused SubString of the person name in #2 above ( All SubStrings were already present) . Now what to do ?

Simple, just add that person name to result , isn't it?

This is a person whose name is not found in UsedMainStringMap as well as we were not able to find a subString of this person name that is not used till now.Hence let's use whole person name .

For example, consider persons joining the call as Rita, Rajiv, Ram .

Rita -> Tageed as r

Rajiv tagged as -> ra

Now when we try to execute the logic for Ram .

We execute #1 for Ram and found that , Ram is not there.

In Step #2 , we try to use substring r & ra and find that they are already there.

So code modified to :

List<String> result = new ArrayList<String>(); Map<String, Integer> usedMainStrings = new HashMap<String, Integer>(); Map<String, String> usedSubStrings = new HashMap<String, String>(); result.add(names.get(0).substring(0, 1)); addUsedMainString(usedMainStrings, names.get(0)); addUsedSubStrings(usedSubStrings, names.get(0)); for (int i = 1; i < names.size(); i++) { String next = names.get(i); Integer occurence = usedMainStrings.get(next); if (occurence != null && occurence > 0) { occurence++; result.add(next + " " + occurence); } else { boolean subStringAdded = false; for (int j = 1; j <= next.length(); j++) { String nextSubString = next.substring(0, j); if (!usedSubStrings.containsKey(nextSubString)) { subStringAdded = true; result.add(nextSubString); break; } } //This String has not been used nor we were successful in finding its subString..so add it directly if (!subStringAdded) result.add(next); } addUsedMainString(usedMainStrings, next); addUsedSubStrings(usedSubStrings, next); } return result;

 The Code is available here in github.

You can download and use input from here to execute and validate it .


If you have any suggestions or inputs, please use the comment section below .Thanks for reading through !