CareerCup

By chain, do you mean the following statement:
If we remove a character from string S1 and it becomes S2, next time do we have to only remove a character from S2 and making another word in the inventory ?

If so, here's my dynamic programming approach:

- Sort words by their size (from smallest to longest).
- then, define dp[i] = The longest chain that can be formed from word[0] up to word[i] and ends at word[i].
- now, dp[i] = max( dp[j]+1) from all j from 0 to i, provided that by removing one character from word[i] we can have word[j].(we can use a hash map for checking this condition)
- final answer is max(dp[i]) 0<=i<N.
- The order is O(N*L*L), which N is the number of words and L is the maximum length of words.

#include <bits/stdc++.h>

using namespace std;

const int maxn=10000;

unordered_map< string,int > hashTable;
int dp[maxn];

int LongestChain(vector<string> V)
{

	vector< pair<int,string> > list;
	for (auto s:V){
		list.push_back({s.size(),s});
	}
	sort(list.begin(),list.end());
	
	int N=list.size();
	hashTable.insert( {list[0].second,0} );
	dp[0]=1;

	int answer=dp[0];

	for (int i=1;i<N;i++){
		dp[i]=1;
		string s=list[i].second;
		
		int size = s.size();
		for (int j=0;j<size;j++){
			
			string tmpStr = s;
			tmpStr.erase(tmpStr.begin()+j);
			auto it = hashTable.find(tmpStr);

			if (it!=hashTable.end())
				dp[i] = max (dp[i],dp[it->second]+1);
		}
		answer = max ( answer , dp[i]);

		hashTable.insert({s,i});

	}

	return answer;
}



int main()
{

	int N;
	cin >> N;
	vector<string> V(N);
	for (int i=0;i<N;i++)
		cin >> V[i];

	cout << LongestChain(V) << endl;


	return 0;
}

If i am not wrong, it can be solved much easier -
Record < string,string_len> for each word;
Sort the container according to string_len in non-decreasing order.
starting from beginning, search for longest increasing subarray and keep track or maximum length subarray.
return maxlen subarray.

If the words/strings in the library are all subsets of each other, then the longest possible chain will be n.
E.g. If the words are: a, ab, abc, abcd, abcde, abcdef, .... ,abcde..xyz. You have 26 words (n = 26). Start with the last word and remove the char z, it will now be the same as the second last word. Now remove the char y, it will be same as third last word and so on till we reach the first word a. So the longest possible chain is n

Can't come up with a more efficient solution than the dynamic programming approach, but as an alternative, you can model the problem as a graph problem. More specifically, by building one or more acyclic directed graphs in this manner:

1. For each word, associate it with a graph node.
2. For each word, generate the list of words that can be derived from it based on the problem's rule (i.e. take one character out from each character position). Compare these to the rest of the words. For each match, link the node together, with the parent being the longer word.
3. Once you've passed through every word in (2), you'll have one or more ADGs and a list of nodes from said ADGs, but no knowledge of "root" nodes. But this doesn't matter.
4. For each node, compute its "longest distance to a leaf node"; you can use a cache of nodes:longest-distance to avoid doing duplicate computation for a given node.

The answer is the biggest number you find while iterating through nodes in step (4).

In Java:

import java.util.*;

/**
 * Given a list of words, you can select any one word and remove a character from
 * it such that it becomes another word in the library. Selected word is then discarded.
 * You can then do the same with the new word in the latter.
 *
 * Now, given an arbitrary library of words, what is the longest chain of words you can
 * play this game with?
 *
 * e.g.:
 * For the library of words: ['a', 'aa', 'bb', 'bbc', 'cbbc'], the longest chain is 3 words
 * because 'cbbc' -> 'bbc' -> 'bb' is the longest chain you can make out of the input set.
 *
 * (NOTE) This solution uses acyclic directed graph build-and-search method, and assumes
 *        or eliminates duplicate words.
 */
public class WordChainADG {

    // the list of input words, in no particular order
    private List<String> words;

    public WordChainADG() {
    }

    public int longestChain(List<String> words) {
        // initialize our scratch spaces
        words = new ArrayList<String>(words);
        HashMap<String, Node> nodes = new HashMap<String, Node>();          // mapping each word to a node
        HashMap<Node, Integer> chainLengths = new HashMap<Node, Integer>(); // mapping each node to its longest chain length

        int n = words.size();

        // initialize the maps: create node for each word
        for (String word : words) {
            nodes.put(word, new Node(word));
        }
        // and a count of longest-chain-length for each node
        for (String word : nodes.keySet()) {
            Node node = nodes.get(word);
            chainLengths.put(node, 0);  // 0 indicates not yet determined
        }

        // build the (ADG) graphs
        for (int i = 0; i < n; i++) {
            String word = words.get(i);
            int wordSize = word.length();
            // try removing each character in the current word, and see if it matches any of the shorter words
            for (int j = 0; j < wordSize; j++) {
                String tempstr = trimCharacterAt(word, j);
                Node node = nodes.get(tempstr);
                if (node != null) {
                    // such a word exists! add the associated node to this word's node children
                    nodes.get(word).addChild(node);
                }
            }
        }

        // now we have 1 or more (ADG) graphs whose edges point from longer words to shorter words
        // we need to find the maximum path in each graph, and then find the maximum of those maximum paths

        int answer = 0;
       
        // each node can be thought of as the root of a tree/ADG; so all we have to do is to find
        // the maximum-path-to-a-leaf of each "root" and record the biggest number seen
        HashSet<Node> allNodes = new HashSet<Node>(chainLengths.keySet());
        for (Node node : allNodes) {
            int longestPath = findLongestPath(node, chainLengths);
            chainLengths.put(node, longestPath);
            
            if (longestPath > answer) {
                answer = longestPath;
            }
        }

        System.out.println(chainLengths);

        return answer;
    }

    // given a string, and an index within that string, take out
    // the character on that index, and return the resulting string
    private static String trimCharacterAt(String input, int index) {
        if (index < 0 || index >= input.length()) {
            throw new IndexOutOfBoundsException();
        }
        char[] astr = new char[input.length() - 1];
        for (int i = 0, j = 0; i < input.length(); i++) {
            if (i == index)
                continue;
            astr[j++] = input.charAt(i);
        }
        return new String(astr);
    }

    // a simple graph node in an ADG; associated with a word, and 
    // can have 0-N children (pointees of its outgoing edges)
    private class Node {
        private String word;
        private ArrayList<Node> children;
        public Node(String word) {
            this.word = word;
            children = new ArrayList<Node>();
        }
        public List<Node> getChildren() {
            return children;
        }
        public void addChild(Node child) {
            children.add(child);
        }
        @Override
        public String toString() {
            return "<Node(\"" + word + "\")>";
        }
    }

    // given a node, find the longest path to a leaf;
    // since we can assume that, starting from `node` the graph is ADG, we don't have to worry
    // about cycles; additionally once the longest path of a node is computed, we can update
    // this value in the cache given (`longestPaths`) so that the same computation for a given
    // node is not repeated
    private static int findLongestPath(Node node, Map<Node, Integer> longestPaths) {
        int computed = longestPaths.get(node);
        if (computed != 0) {
            // already determined
            return computed;
        }
        List<Node> children = node.getChildren();
        // base case
        if (children.size() == 0) {
            longestPaths.put(node, 1);
            return 1;
        }
        // recursive case
        int childPath = 0;
        for (Node child : node.getChildren()) {
            int childLongestPath = findLongestPath(child, longestPaths);
            if (childLongestPath > childPath) {
                childPath = childLongestPath;
            }
        }
        assert (childPath > 0);
        longestPaths.put(node, 1 + childPath);
        return 1 + childPath;
    }

    public static void main(String[] args) {
        List<String> words = new ArrayList<String>();
        Scanner input = new Scanner(System.in);
        while (input.hasNext()) {
            String word = input.next();
            words.add(word);
        }

        int answer = new WordChainADG().longestChain(words);
        System.out.println("Longest chain: " + answer);
    }

}

public static int getLongestChainKLength(String[] words){

List<String> wordList = Arrays.asList(words);
Collections.sort(wordList,new Comparator<String>() {

@Override
public int compare(String str1, String str2) {

return str1.length()-str2.length();
}
});
Map<String ,Integer> map = new HashMap<String ,Integer>();
map.put(wordList.get(0),1);

int[] dp = new int[wordList.size()];
dp[0] =1;
int ans =dp[0];

for(int i=1;i < wordList.size();i++){

dp[i] =1;
String s = wordList.get(i);
int size = s.length();

for(int j=0;j<size;j++){

String newString = s.substring(0, j) + s.substring(j+1);

if(map.containsKey(newString)){

dp[i]= Math.max(dp[i], map.get(newString)+1);

}
}
ans = Math.max(ans, dp[i]);
map.put(s, dp[i]);
}

return ans;
}

public static int getLongestChainKLength(String[] words){
		
		List<String> wordList = Arrays.asList(words);
		Collections.sort(wordList,new Comparator<String>() {

			@Override
			public int compare(String str1, String str2) {
				 
				return str1.length()-str2.length();
			}
		});
		Map<String ,Integer> map = new HashMap<String ,Integer>();
		map.put(wordList.get(0),1);
		
		int[] dp = new int[wordList.size()];
		dp[0] =1;
		int ans =dp[0];
		
		for(int i=1;i < wordList.size();i++){
			
			dp[i] =1;
			String s = wordList.get(i);
			int size = s.length();
			
			for(int j=0;j<size;j++){
				
				String newString =  s.substring(0, j) + s.substring(j+1);
				
				if(map.containsKey(newString)){
					
					dp[i]= Math.max(dp[i], map.get(newString)+1);
					
				}
			}
			ans = Math.max(ans, dp[i]);
			map.put(s, dp[i]);
		}
		
		return ans;
	}