Popular Posts

Tuesday, May 29, 2012

Maximum size name chopping

In the hidden country of Lapatrecta, an age old custom was followed to ensure that no outsider ever entered their country undetected. The security measure, though simple, was an effective one. Every person born in Lapatrecta had the initials of all his forefathers included in front of his name. Every once in a while, certain families became very famous and the initials of their ancestors were dropped from the names of all their descendants. Thus, there existed a nice homogeneity in the names of the people of Lapatrecta.
Now, a royal ball was organized at the behest of the Queen of Lapatrecta and all citizens were cordially invited to the event. The ball was being held to chop off the initials of the ancestors of the most distinguished family of the country. The Queen set the following 2 criteria for determining the most distinguished family from amongst the invitees:
1. The family must have more than 1 member living.
2. The length of the ancestor list of the family must be as long as possible.
For example:
For 3 people:

APJQ Ravi

APJRS Rahul

PJQ Bharat

Refer : http://www.codechef.com/problems/INSOMA4
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class NameChopping {

public static void main(String[] args) {

BufferedReader reader = new BufferedReader(new InputStreamReader(
System.in));
try {
int inputSize = Integer.parseInt(reader.readLine());
List<String> names = new ArrayList<String>();
for (int i = 0; i < inputSize; i++) {
names.add(reader.readLine());
}
// sort the string
Collections.sort(names);
getMaxSizeOfAncestors(names, inputSize);
} catch (Exception e) {
e.printStackTrace();
}

}

static void getMaxSizeOfAncestors(List<String> pNames, int collectionSize) {
int maxCount = 0;

// Check the starting letters of the names.If any two names have the
// same starting alphabets, then increase the count of maximum size.
for (int i = 1; i < collectionSize; i++) {
int tracker = 0;// temp variable
while (tracker < pNames.get(i - 1).length()
&& tracker < pNames.get(i).length()
&& pNames.get(i).charAt(tracker) == pNames.get(i - 1)
.charAt(tracker)) {
tracker++;
}

if (tracker > maxCount)
maxCount = tracker;
}
System.out.println(maxCount);
}

}

No comments:

Post a Comment