CareerCup

public String findLCS(String a, String b) {
		if (a == null || b == null ||
			a.length() == 0 || b.length() == 0) {
				return "";
		}
		
		Map<Character, Integer> map = new HashMap<>();
		for (int i = 0; i < b.length(); ++i) {
			map.put(b.charAt(i), i);
		}
		
		String lcs = null;
		int count = 0;
		for (int i = 0; i < a.length(); ++i) {
			if (map.containsKey(a.charAt(i))) {
				if (count != 0 && map.get(a.charAt(i - 1)) + 1 == map.get(a.charAt(i))) {
					++count;
				} else {
					count = 1;
				}
				
				if (lcs == null || lcs.length() < count) {
					lcs = a.substring(i - count + 1, i + 1);
				}
			} else {
				count = 0;
			}
		}
				
		return lcs;
	}

O(N) time, O(N) space

Why (Talented?)People from Indian R&D centers asks diffcult(actually nonsense) questions  as compared to US and Europe R&D centers of same company?

Why (Talented?)People from Indian R&D centers asks diffcult(actually nonsense) questions as compared to US and Europe R&D centers of same company?

Since the all the letters in the second string are distinct the problem can be reduced to longest increasing sub sequence(nlogn)

Make and array where arr[i] is the index of the letter a[i] in b
and find its LIS in nlogn

KMP algorithm

en.m.wikipedia.org/wiki/Knuth–Morris–Pratt_algorithm

Why People from Indian R&D center always ask difficult(read as Nonsense) question as compared US, Europe R&D centers of same company :) ...

Why (Talented?)People from Indian R&D centers asks diffcult(actually nonsense) questions  as compared to US and Europe R&D centers of same company?

Use binary tree to organize b, for each char in a, do a search in b in log(n) time and do a comparison. O(nlogn)

Hi,
What do u mean by all distinct characters.Does that mean the string b has all of the characters appearing exactly once?

@ siva.sai, what do you mean by "Expected complexity O(nlogn)"?
MIT teaches that best known algo for LCS today is O(n^2).
youtu.be/ocZMDMZwhCY?t=27m54s

c# implementation.
Longest Common Subsequence's length.
Classic algo, O(m*n).

using System;

namespace LongestCommonSubsequence {

    class Program {

        private static int LCSsLength( string s1, string s2 ) {

            int[,] arr = new int[ s1.Length + 1, s2.Length + 1];

            int[] maxValCoords = new int[2];
            int maxVal = 0;

            for ( int row = 0; row < s1.Length; row++ ) {
                for ( int col = 0; col < s2.Length; col++ ) {

                    var leftCell = arr[ row + 1, col ];
                    var upCell = arr[ row, col + 1 ];
                    var leftDiagonalCell = arr[ row, col ];

                    if ( s1[ row ] != s2[ col ] ) { 
                        arr[ row + 1, col + 1 ] = Math.Max( leftCell, upCell );
                    } else {
                        arr[ row + 1, col + 1 ] = leftDiagonalCell + 1;
                    }

                    var currVal = arr[ row + 1, col + 1 ];

                    if ( currVal < maxVal ) { continue; }

                    maxValCoords[ 0 ] = row + 1;
                    maxValCoords[ 1 ] = col + 1;
                }
            }
            
            return GetVal( arr, maxValCoords, s1, s2 ).Length;
        }

        private static string GetVal( int[,] arr, int[] coords, string s1, string s2 ) {

            string commonChar = string.Empty;
            var row = coords[ 0 ];
            var col = coords[ 1 ];

            if ( arr[ row, col ] == 0 ) return string.Empty;
            
            var leftCell = arr[ row, col - 1 ];
            var upCell = arr[ row - 1, col ];

            var chFromS1 = s1[ row - 1 ];
            var chFromS2 = s2[ col - 1 ];

            if ( chFromS1 == chFromS2 ) {
                commonChar = chFromS2.ToString();
                row--;
                col--;
            }
            else if ( upCell >= leftCell ) { row--; }
            else { col--; }

            return GetVal( arr, new[] { row, col }, s1, s2 ) + commonChar;
        }

        static void Main( string[] args ) {
            var res = LCSsLength("MICHAELANGELO","HIEROGLYPH");
            Console.ReadLine();
        }
    }
}

P N algorithm shall work here.

Can be done in O(n) using hachMap:

def maxCommonSubString(S1,S2):
##Assuming S2 has all unique chars
S2Dic = {S2[i]:i for i in xrange(len(S2))}
maxR = 0
subS = ''
i = 0
while i < len(S1):
if S1[i] in S2Dic:
j = S2Dic[S1[i]]
k = i
while j < len(S2) and k < len(S1) and S1[k] == S2[j]:
k += 1
j += 1
if k - i > maxR:
maxR = k-i
subS = S1[i:k]
i = k
else:
i += 1
return subS

It can be done in O(n) using hashmap

def maxCommonSubString(S1,S2):
    ##Assuming S2 has all unique chars
    S2Dic = {S2[i]:i for i in xrange(len(S2))}
    maxR = 0
    subS = ''
    i = 0
    while i < len(S1):
        if S1[i] in S2Dic:
            j = S2Dic[S1[i]]
            k = i
            while j < len(S2) and k < len(S1) and S1[k] == S2[j]:
                k += 1
                j += 1
            if k - i > maxR:
               maxR = k-i
               subS = S1[i:k]
            i = k
        else:
            i += 1
    return subS

Isn't the following an O(n) solution? It requires O(n) space though.

public int lcString(String a, String b) {
    Map<Character, Integer> map = new HashMap<>();
    
    // Store a in the map
    for (int i = 0; i < a.length; i++) {
        map.add(a.charAt(i), i);
    }
    
    // for each character in b, see if it is occurring linearly in the map
    int lcs = 0, currLcs = 0;
    Integer oldLocation = -1, newLocation = -1;
    for (int i = 0; i < b.length; i++) {
        newLocation = map.get(b.charAt(i));
        if ((newLocation != null) && (newLocation == oldLocation+1)) // increasing
            currLcs++;
        else {
            if (lcs < currLcs)
                lcs = currLcs;
            currLcs = 0;
        }
        
        oldLocation = newLocation;
    }
    
    // currLcs will be greater than lcs if the common string
    // ends at the termination of both strings
    return (currLcs > lcs) ? currLcs : lcs;
}