CareerCup

Construct the suffix array and sort it. This solution is O(NlogN):

public static void main(String argv[])
        {
            String s = "banana";

            List<String> suffixArray = new ArrayList<String>();

            for(int i=0; i<s.length(); i++)
            {
                suffixArray.add(s.substring(i, s.length()));
            }

            Collections.sort(suffixArray);

            String repeat = "";
            int longest = 0;

            for(int i=1; i<suffixArray.size(); i++)
            {
                String str1=suffixArray.get(i-1);
                String str2=suffixArray.get(i);
                int matchLength = 0;
                for(;matchLength<Math.min(str1.length(), str2.length()); matchLength++)
                {
                    if(str1.charAt(matchLength)!=str2.charAt(matchLength)) break;
                }

                if(matchLength>longest)
                {
                    longest = matchLength;
                    repeat = str1.substring(0,matchLength);
                }
            }

            System.out.println("Answer:"+repeat);

}

An ideal solution on top of my head is: suffix tree. Suffix tree can be constructed in a linear way, and find the largest repetitive string can be done through a linear traversal of suffix tree. However suffix tree is very difficult to implement during the interview period.

My solution starts with the largest possible repeating string (length-1) and returns a repeat if found, null otherwise. I think this performance is O((n-1)!) where n is the number of characters in the string. I'm on this site trying to practice and learn, so welcome all constructive feedback and correction :)

protected string LongestRepeatString(string baseString)
    {
        int checkLen = baseString.Length - 1; 

        while (checkLen > 0)
        {
            for (int i = 0; i <= baseString.Length - checkLen; i++)
            {
                string str = baseString.Substring(i, checkLen);
                for (int j = i + 1; j <= baseString.Length - checkLen; j++)
                {
                    string str2 = baseString.Substring(j, checkLen);
                    if (str.Equals(str2))
                        return str;
                }
            }
            checkLen--;
        }
        return null;
    }

Hmm, nontrivial. Let's try this in Python. Makes everything easier.

Start by checking substrings one less than the length of the string for repeats, then reduce the maximum substring size by 1 each iteration until you find one that's repeated. It's something like O(n!), but it gets the job done.

def maxRepeatedSubstring(repeatedString):
	maxSubstringLength = len(repeatedString)-1
	while maxSubstringLength>0:
		startPoint = 0
		while startPoint+maxSubstringLength<=len(repeatedString):
			substringToMatch = repeatedString[startPoint:startPoint+maxSubstringLength]
			if substringToMatch in repeatedString[startPoint+1:]
				return substringToMatch
			startPoint+=1
		maxSubstringLength-=1
	return None

You can find every subsequence and then select the longest one which is repeated at least once. O(n^2) time and O(n^2) space in Python:

def getLRS(strIn):
	lrs = {}
	for i in range(len(strIn)):
		start = strIn[i]
		if start not in lrs:
			lrs[start] = 0
		lrs[start] +=1
		for j in range(i+1, len(strIn)):
			start += strIn[j]
			if start not in lrs:
				lrs[start] = 0
			lrs[start] +=1
	winner = ""
	maxLen = - 1
	for k in lrs:
		if winner == "":
			winner = k
		if lrs[k] > 1:
			if len(k) > maxLen:
				maxLen = len(k)
				winner = k
	return winner

My first instinct is that it has similarities with string matching algorithms, specifically Rabin-Karp, which uses hashes to compare strings. So, if you start with that as a base concept, you can then perform rounds of matching, throwing away your data structures as necessary. This keeps your memory bounded for very large strings as well.

I neglected the hash() below, by just storing the string itself. But you can save the total amount of memory that you're using at any given time by cleaning up your data structure after each round.

Worst case, you've got a decreasing amount of memory usage at any given time. I have a hard time characterizing it, but it's a recurrence [ O(2*(N-1)) + O(3*(N-2)) ... ] that ends with O(N). I think that's what it all boils down to.

Processing time is O(N^2) for the nested loops. Lines of code could be reduced, but I left it this way for clarity.

Python:

def findLongestRepeat(str):
    s = set()

    # Loop from N-1 chars to 0
    for i in xrange(len(str)-1, 0, -1):
        print(len(s))

        # Clear our data structure since it's no longer needed
        s.clear()

        # Initial conditions
        start = 0
        stop = start+i

        # Until the end index isn't beyond our string
        while stop != len(str)+1:

            # Get a substring
            substr = str[start:stop]
            if substr in s:
                print substr
                return
            else:
                s.add(substr)

            stop += 1
            start += 1

en.wikipedia.org/wiki/Longest_repeated_substring_problem

banana – largest repetitive sequence is 'a'.

public static String getMaxRepeatedString(String input) {
		int k = input.length() / 2;
		Map<String, Integer> countMap = new LinkedHashMap<String, Integer>();
		while (k > 0) {
			for (int i = 0; i <= input.length() - k; i++) {
				String substr = input.substring(i, i + k);
				Integer in = countMap.get(substr);
				if (in == null) {
					countMap.put(substr, 1);
				} else {
					countMap.put(substr, in + 1);
				}
			}
			k--;
		}
		System.out.println("-" + countMap);
		String bigStr = "";
		int big = 0;
		for (Map.Entry<String, Integer> entry : countMap.entrySet()) {
			if (entry.getValue() > big) {
				big = entry.getValue();
				bigStr = entry.getKey();
			} 
		}
		return bigStr;
	}

Algorithm
1. First have count array for the characters
banana -> b=1, a=3, n=2
2. Scan the string, if a character or a sequence of characters have occurrences of more than 1 then push that string to hash map.
start with b, b has one so reject b,
start with a, a has more than 1, push it hash map
n, has more than 1, pust it to hash map, also
compute an , push it to hash map
a, a has more than 1, map already has the entry,
compute ana, push it to hash map
n, n has more than 1, map already has the entry,
compute anan, check if palindrome, yes , increment the count for an in the hash map, and push anan to hashmap
a, a has more than 1, map already hash the entry,
compute anana, check if palindrome, yes, increment the count for ana, in the hash map, and push anana to hashmap.

now traverse the map and see the max count and the length of the string.

protected void Page_Load(object sender, EventArgs e)
        {
            // Input array that contains duplicate strings. b-a-n-a-n-a
            ////remove 1 letter at a time
            string[] array3 =
            {
                "b", "ba", "ban", "bana", "banan", "banana", "a", "an", "ana", "anan", "anana", "n", "na",
                "nan", "nana", "a", "an", "ana", "n", "na", "a"
            };
            List<string> list3 = array3.ToList();
            List<string> Answer3 = HasDuplicates(list3);
            // Display the array.
            Console.WriteLine(string.Join(",", array3));
            Console.WriteLine(Answer3.ToArray().Distinct());
            Console.ReadKey();
        }

        private List<string> HasDuplicates(List<string> notDistinct)
        {
            List<string> vals = new List<string>();
            notDistinct.Sort();
            for (int i = 0; i < notDistinct.Count; i++)
            {
                if (notDistinct.IndexOf(notDistinct[i]) < notDistinct.LastIndexOf(notDistinct[i]))
                {
                    vals.Add(notDistinct[i]);
                }
            }
            return vals;
        }

This would have been my interview response -- best I could think of with no prep or lookup...

import java.util.Stack;


public class RepeatedSubstring {

	public static boolean isDupSubstr(String s, String lookup) {
		int found = 0;
		int other = 0;
		found = s.indexOf(lookup);
		other = s.lastIndexOf(lookup);
		if (found != other) return true;
		else return false;
	}
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		String s = "banana";
		String sub = "ana";
		Stack<String> subs = new Stack<String>();
		for (int i = 0; i < s.length(); i++) {
			String lookup = s.substring(i);
			if (isDupSubstr(s, lookup)) {
				subs.push(lookup);
			}
		}
		for (int i = s.length() - 1; i >= 0; i--) {
			String lookup = s.substring(0, i);
			if (isDupSubstr(s, lookup)) {
				subs.push(lookup);
			}
		}
		int maxLen = Integer.MIN_VALUE;
		String longestSub = null;
		while (!subs.isEmpty()) {
			String entry = subs.pop();
			if (entry.length() > maxLen) {
				maxLen = entry.length();
				longestSub = entry;
			}
		}
		if (maxLen == Integer.MIN_VALUE) {
			System.out.println("There is no repeating substr.");
		}
		else {
			System.out.println("The longest repeating substr is : " + longestSub + ".");
		}
	}
}

Not the most efficient solution out there, but a college kid could maintain it.

public static String findLargestDuplicate(String intput) {
        String selected = null;
        for (int i = 0; i < intput.length(); i++) {
            String s = intput.substring(i, i + 1);
            for (int j = i + 1; j < intput.length(); j++) {
                String aux = intput.substring(i, j + 1);
                if (intput.indexOf(aux, i + 1) >= 0) {
                    s = aux;
                } else {
                    break;
                }
            }
            if (selected == null || selected.length() < s.length()) {
                selected = s;
            }
        }
        return selected;
    }