Category Archives: Programming

Home / Programming
2 Posts

The following presents my solution for the Longest Chain of Character Removals problem.

Problem Statement

You are given a library with n words (w[0], w[1], ...,w[n-1]). You choose a word from it, and in each step, remove one letter from this word only if doing so yields another word in the library. What is the longest possible chain of these removal steps?

Constraints:

  • 1 <= n <= 50000
  • 1 <= the length of each string in w <= 50
  • Each string is composed of lowercase ascii letters only

The function should take in an array of strings w as its argument and should return a single integer representing the length of the longest chain of character removals possible.

Example input/output

a
b
ba
bca
bda
bdca

Calling the function on the input above should output 4. The longest possible chain is "bdca" -> "bca" -> "ba" -> "a".

Solution

I solved this problem using dynamic programming (DP):

1. Sort the input dictionary by size, from shortest to longest
2. Create a dynamic programming table, which I call chainLength of size n. Define chainLength[i] to be the length of the longest chain of character removals that can be formed starting with w[i] in the sorted input dictionary.
3. Use an unordered_map (hash table) to keep track of words in the input dictionary that have already been processed by the DP algorithm. The key value is the word from the input dictionary and the mapped value is the longest possible chain starting with that word (same value as stored in the DP table)
4. Iterate through every word in the sorted input dictionary and find the longest possible chain up to that word. In other words, fill up from DP table going from index 0 to n-1.
5. To calculate chainLength[i] in the dynamic programming table, iterate through each letter of w[i] and check if removing that letter would yield another word in the dictionary. This can be done in constant time using the hash table. If removing a letter from w[i] yields w[j], then it is possible to create a chain with length 1 + chainLength[j]. (Note that in this scenario j will always be less than i because the input is sorted by length and so the DP algorithm will process the shorter words first) By doing this for every letter, we can find the longest possible chain starting with w[i].
5. The result is the maximum value in the dynamic programming table chainLength

Code

I recently solved an interesting programming challenge, called Friend Circles, and wanted to share my solution, which was implemented in C++.

Problem statement

There are N students in a class. Some of them are friends, while some of them are not. Their friendship is transitive in nature, i.e., if A is a friend of B and B is a friend of C, then A is also a friend of C. A friend circle is a group of students who are directly or indirectly friends.

You have to complete a function int friendCircles(vector<std::string> friends) which returns the number of friend circles in the class. Its argument, friends, is an array of strings. However, for the sake of this problem, friends should be viewed as a 2-dimensional array of characters (the input has N strings and each string has N characters). Therefore, friends is a NxN matrix which consists of characters 'Y' or 'N'. If friends[i][j] = 'Y', then students i and j are friends which each other, otherwise not. You have to return the total number of friend circles in the class.

Constraints:

  • 1 <= N <= 300
  • Each element of matrix friends will be either'Y' or 'N'
  • Number of row and columns in friends will be equal
  • friends[i][i] = 'Y', where 0 <= i < N
  • friends[i][j] = friends[j][i]

Example inputs/return values

Example 1

YYNN
YYYN
NYYN
NNNY

should output 2. There are two pairs of friends (0, 1) and (1, 2). So (0, 2) is also a pair of friends by transitivity. So the first friend circle contains (0, 1, 2) and the second friend circle contains only student 3.

Example 2

YNNNN
NYNNN
NNYNN
NNNYN
NNNNY

should output 5 because no student is friends with any other. So each student forms its own friend circle, for a total of 5.

Solution (C++)

Note that, since friends is an NxN matrix where friends[i][j] = friends[j][i], the input can be thought of as an undirected graph. Each student represents a node in the graph and there is an edge between two nodes if the corresponding students are friends. If there is a path in the graph from student A to student B, then, by transitivity, students A and B must be in the same friend circle. Therefore, we can use a DFS/BFS to find each student in a friend circle. The general algorithm for this problem can be represented as follows:

1. Create an array to keep track of whether a student has been visited by the DFS/BFS. This can also be thought of to represent whether or not that student has already been placed in a friend circle.
2. Starting with the first student, use a DFS to find each student in the same friend circle. Mark each student as being "visited".
3. Increment the number of friend circles.
4. Repeat steps 2 and 3, starting with the next student that is not already part of a friend circle.

(For those more familiar with graph theory, note that each friend circle would constitute a connected component on the graph. Therefore, this problem can be abstracted out to be the same as "How to find the number of connected components in an undirected graph". )