[f]izzbuzzer

Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

Chain names challenge

Sharing is caring!

Problem statement
You’re given an array of names, where each name is given as a string. Your task is to link these names into a chain, so that the $i^{th}$ name starts with the same letter the $(i - 1)^{th}$ name ends, and return this chain as a list.

All names should be used. It is guaranteed that each name starts with a unique letter. It is also guaranteed that there is only one solution.

Sample Input 0

Raymond
Nora
Daniel
Louie
Peter
Esteban

Sample Output 0

Peter Raymond Daniel Louie Esteban Nora

Sample Input 1

Yee
Estelle
Vickey

Sample Output 1

Vickey Yee Estelle

Sample Input 2

Haydee
Tai
Elliott
Inocencia
Archie

Sample Output 2

Haydee Elliott Tai Inocencia Archie

$\mathcal{O}(n^2)$ solution with $\mathcal{O}(1)$ additional space
We will start building our chain by trying out every name in the list as the head element. That is, we are going to iterate over all the names s in our names list N and append any unused names to the current chain that meet the criteria (last character in chain must be equal to first character of unused name). Every time we append a new name to our current chain we restart the search for a new name that we can append, while also checking whether we have used all names (length of chain must be equal to names list length). If we have exhausted our search without any luck (i.e. did not use all the names in the names list), we repeat the process using a different name as the head element of our chain. So for the following example:

Yee
Estelle
Vickey

The iteration stages will look as follows:

s = Yee
chain = Yee Estelle
s = Estelle
s = Vickey
chain = Vickey Yee
chain = Vickey Yee Estelle

At first we start a chain using Yee as head. Then we append Estelle since the last character of Yee matches the first character of Estelle and the chain becomes Yee Estelle. Now, for the last character of the chain we cannot find a new name to append. Next, we start a chain using Estelle as head. Same here. We cannot find a new name to append. Finally we start our chain using the name Vickey. Next we can append the name Yee and then the name Estelle. Since our chain has the same length as our input list, we know that we are done and return the current chain.

The full code is listed below.

Full code $\mathcal{O}(n^2)$ solution with $\mathcal{O}(1)$ additional space

public class ChainNames {
private static String[] chainNames(String[] N) {
for (String s : N) {
for (int i = 0; i < N.length; i++) {
if (!s.contains(N[i]) && s.toUpperCase().charAt(s.length() - 1) == N[i].charAt(0)) {
s = s + " " + N[i];
if (s.split(" ").length == N.length) {
// We have used all the names. Return result.
return s.split(" ");
}

// Since we have updated our s, we need to restart the inner loop by setting i=-1
// and continue searching for a new name to append to the existing s.
i = -1;
}
}
}

return N;
}

public static void main(String[] args) throws FileNotFoundException {
System.setIn(new FileInputStream(System.getProperty("user.home") + "/" + "in.txt"));
Scanner in = new Scanner(System.in);

List nameList = new ArrayList<>();
while (in.hasNext()) {
String name = in.next();
nameList.add(name);
}

// Convert list to array
String[] names = new String[nameList.size()];
for (int i = 0; i < names.length; i++) {
names[i] = nameList.get(i);
}

String[] ans = chainNames(names);
for (String name : ans) {
System.out.print(name + " ");
}

}
}

$\mathcal{O}(n)$ solution with $\mathcal{O}(n)$ additional space
There is also a solution with $\mathcal{O}(n)$ running time, but with an additional $\mathcal{O}(n)$ space.

We will iterate over all the names in the input list and are going to store all possible trailing characters (name.charAt(name.length()-1)) in a Set called last. We will also do a similar thing for the leading/first characters of a name (name.charAt(0)). Although we will store each first character in a Map first, with first[ch] pointing to the name that begins with the character ch. That way we can easily find a matching name for some character.

Map first = new HashMap<>();
Set last = new HashSet<>();
for (String name : names) {
char ch = name.charAt(0);
first.put(ch, name);

ch = name.toUpperCase().charAt(name.length() - 1);
last.add(ch);
}

Next, we are going to find the head of the chain. Since according to the problem statement, it is guaranteed that there is only one solution, we know that only one name can be the head of the chain. In order to find the head of the chain we are going to search for a name whose first character does not appear in last.

String head = null;
for (String name : names) {
char firstChar = name.charAt(0);
if (!last.contains(firstChar)) {
head = name;
break;
}
}

Note: There cannot be a head whose first character appears in last for some other name.
Proof: Consider the chain AB BC CA in which the first character of AB is equal to the last character of CA. But now we can just rotate our chain one position to the right making it CA AB BC (since we can insert CA in front of AB BC). CA AB BC is also a valid chain. Also note that if AB is the head, then CA has do be at the right-end of the chain. That is because if CA were to be between other names in the chain, like for instance in AB ... CA AZ ..., it would be a contradiction to the problem's statement that each name starts with a unique letter, since AZ would also start with the letter A. And because CA always has to be at the right-end of the chain when AB is head, it is always possible to rotate the chain and move CA in front of AB creating another possible solution which would contradict the problem's statement that it is guaranteed that there is only one solution.

Once we have our head element we can start constructing the rest of the chain. We start by taking the last character in the current chain (at the beginning this is head) and search for a name that begins with that character. We do that using first. Once we find such a name, n, we append it to the chain and note it using a backtracking map with backtracking[n] pointing to the previous name. For example, backtracking['Inocencia'] = 'Tai', since 'Tai' precedes 'Inocencia' in the final chain. We then delete n from first and repeat until first does not contain any matching names for the current last character.

Map backtracking = new HashMap<>(); // for a sequence name_i, name_j: map[name_j] -> name_i
String tail = head;
char lastChar = tail.toUpperCase().charAt(tail.length() - 1);
while (first.containsKey(lastChar)) {
// If we have a name whose first character is equal to the current chain's last character

String name = first.get(lastChar);

// Point the new name to its previous (which is tail)
backtracking.put(name, tail);

// Set the new name as the new tail
tail = name;

// Remove new name from map
first.remove(lastChar);

// Get last character of the new tail
lastChar = tail.toUpperCase().charAt(tail.length() - 1);
}

Once we are done, we can use backtracking to reconstruct our chain:

String[] ans = new String[names.length];
int cursor = ans.length - 1;
ans[cursor] = tail;
cursor--;
while (tail != null) {
String prev = backtracking.get(tail);
if (prev != null) {
ans[cursor] = prev;
cursor--;
}
tail = prev;
}

return ans;

The full code is listed below.

Full code $\mathcal{O}(n)$ solution with $\mathcal{O}(n)$ additional space

public class ChainNames {
private static String[] chainNames(String[] names) {
Map first = new HashMap<>();
Set last = new HashSet<>();
for (String name : names) {
char ch = name.charAt(0);
first.put(ch, name);

ch = name.toUpperCase().charAt(name.length() - 1);
last.add(ch);
}

// Find the head of the sequence
// If first character of a name does not appear in last-character list then that name must be the head
String head = null;
for (String name : names) {
char firstChar = name.charAt(0);
if (!last.contains(firstChar)) {
head = name;
break;
}
}

Map backtracking = new HashMap<>(); // for a sequence name_i, name_j: map[name_j] -> name_i
String tail = head;
char lastChar = tail.toUpperCase().charAt(tail.length() - 1);
while (first.containsKey(lastChar)) {
// If we have a name whose first character is equal to the current chain last character

String name = first.get(lastChar);

// Point the new name to its previous (which is tail)
backtracking.put(name, tail);

// Set the new name as the new tail
tail = name;

// Remove new name from map
first.remove(lastChar);

// Get last character of the new tail
lastChar = tail.toUpperCase().charAt(tail.length() - 1);
}

String[] ans = new String[names.length];
int cursor = ans.length - 1;
ans[cursor] = tail;
cursor--;
while (tail != null) {
String prev = backtracking.get(tail);
if (prev != null) {
ans[cursor] = prev;
cursor--;
}
tail = prev;
}

return ans;
}

public static void main(String[] args) throws FileNotFoundException {
System.setIn(new FileInputStream(System.getProperty("user.home") + "/" + "in.txt"));
Scanner in = new Scanner(System.in);

List nameList = new ArrayList<>();
while (in.hasNext()) {
String name = in.next();
nameList.add(name);
}

// Convert list to array
String[] names = new String[nameList.size()];
for (int i = 0; i < names.length; i++) {
names[i] = nameList.get(i);
}

String[] ans = chainNames(names);
for (String name : ans) {
System.out.print(name + " ");
}
}
}