Interview Question: Find the Longest Repeating Pattern

October 13, 2012 nateb Interviewing, Technology, 0

Given a string of any size length, find the longest repeating pattern that may be truncated at the end.

To provide examples of expected output:
“abcabc” would be equal to “abc”
“abcdabcdabc” would be “abcd” because the truncation still starts with “abc”

 
public static string FindLongestRepeatingPattern(string input =
    "abcdefghiabcdefghiabcdefghiabcdefghid"+
    "abcdefghiabcdefghiabcdefghiabcdefghi", 
    StringComparison comparison= StringComparison.CurrentCulture)
{
    if (string.IsNullOrEmpty(input))
        throw new ArgumentNullException("input");

    //  Find all possible indices of the string
    var indicies = new List();
    var startChar = char.ToLower(input[0]);
    for (var i = 1; i < input.Length; i++)
    {
        if (startChar == char.ToLower(input[i]))
            indicies.Add(i);
    }

    int longestIndex = -1;
    for (var i = 0; i < indicies.Count; i++)
    {
        //  Take the possible portion
        var substr = input.Substring(0, indicies[i]);

        //  Create a sliding window across the input
        var isMatch = true;
        for (var windowIx = indicies[i]; 
            windowIx < input.Length; 
            windowIx += substr.Length)
        {
            //  Avoid the int overflow bug; 
            //  check if at trucated portion
            if((input.Length - windowIx) < substr.Length)   
            {
                var compareTo = input.Substring(windowIx);
                if (!substr.StartsWith(compareTo, comparison))
                { isMatch = false; break; }
            }
            else
            {
                //  Check if the two strings are equal
                var compareTo = input.Substring(windowIx, substr.Length);
                if (substr.Equals(compareTo, comparison))
                {
                    isMatch = false;
                    break;
                }
            }
        }

        //  We slide across successfully; update the longest index
        if (isMatch)
            longestIndex = i;
    }

    if (longestIndex == -1)
    {
        //  No match found, bail.
        return null;
    }

    //  Return the string
    return input.Substring(0, indicies[longestIndex]);
}

Using BITS Protocol from C# Interview Question: Validate Parantheses Align