// Write a program that finds the number of occurrences of random patterns of a specified length

// in a given string, and return the patterns along with the number of occurrences.

// For example, when searching the string "zfabcde224lkfabc51+crsdtab=", with a specified pattern

// length of 3, the method should return the pattern "abc" with an occurrence value of two.

//

// Implementation details.  A few unanswered questions:

// 1. What to do if the arguments are invalid (string is null, string length is too small, length

//    is too small)?

//  -> For now, I'm just returning an empty result.  An exception may be more appropriate.

//

// 2. How to handle identical strings that overlap (e.g. "ababa" with length 3)?

//  -> I've implemented the class with the option to allow overlaps (default: on)

//

// 3. How to handle case?

//  -> I've implemented the class with the option to ignore case (ie. force all strings to lower

//     case.  default: off)

//

// 4. What string results to return?  Based on the example I wasn't sure if you only wanted strings

//    with more then one occurrence.

//  -> I've implemented the class with the option to specify number of occurrences (default: 1)

//

// Time complexity: O(n) -> Two iterations through array

// Space complexity: O(n) -> Storage of strings in dictionary

​

using System;

using System.Collections.Generic;

​

public class Program {

    public static void Main() {

        Tuple<string, int>[] testTuples = {

            Tuple.Create("zfabcde224lkfabc51+crsdtab=", 3),

            Tuple.Create("ababa", 3),

            Tuple.Create("ab", 2),

            Tuple.Create("", 1),

            Tuple.Create("abcAbc", 3),

            Tuple.Create("alabama", 3),

            Tuple.Create("arearea", 4),

            Tuple.Create("zfabcde224lkfabc51+crsdtab=", 1),

            Tuple.Create("longtest", 20)

        };

        Solution sol = new Solution();

        foreach(Tuple<string, int> tuple in testTuples) {

            List<Tuple<string, int>> result = sol.getSubstringCounts(tuple.Item1, tuple.Item2);

            Console.WriteLine("\"" + tuple.Item1 + "\": (" + tuple.Item2 + ")");

​

            result.Sort();

            foreach(Tuple<string, int> s in result) {

                Console.WriteLine(s.Item1 + " => " + s.Item2);

            }

​

            Console.WriteLine();

        }

    }

}

​

public class Solution {

    private readonly bool allowOverlap; 

    private readonly bool ignoreCase;

    private readonly uint minOccurrences;

​

    public Solution() {

        allowOverlap = true;

        ignoreCase = false;

        minOccurrences = 1;

    }

​

    public Solution(bool allowOverlap, bool ignoreCase, uint minOccurrences) {

        this.allowOverlap = allowOverlap;

        this.ignoreCase = ignoreCase;

        this.minOccurrences = minOccurrences;

    }

​

    public List<Tuple<string, int>> getSubstringCounts(string s, int length) {

        List<Tuple<string, int>> result = new List<Tuple<string, int>>();

​

        if (s == null || s.Length < length || length < 1) {

            // Return an empty result for invalid parameters.

            return result;

        }

​

        // O(n) storage required for all possible substrings

        Dictionary<string, Pair<int, int>> stringPairs = new Dictionary<string, Pair<int, int>>();

        // Iterate through the string with a sliding window of provided length

        // This is an O(n) iteration.

        for (int start=0, end=length; end<=s.Length; start++, end++) {

            string sub = s.Substring(start, length);

            if (ignoreCase) {

                sub = sub.ToLower();

            }

​

            Pair<int, int> val; // Item1 = counter, Item2 = end index of last occurrence

            if (stringPairs.TryGetValue(sub, out val)) {

                // We ignore the string if it starts before the previous one ends if we don't

                // allow overlaps.

                if (allowOverlap || start >= val.Item2) {

                    val.Item1 += 1;

                    val.Item2 = end;

                    stringPairs[sub] = val;

                }

            }

            else {

                stringPairs.Add(sub, new Pair<int, int>(1, end));

            }

        }

​

        // Another O(n) iteration

        foreach(KeyValuePair<string, Pair<int, int>> entry in stringPairs) {

            if (entry.Value.Item1 >= minOccurrences) {

                result.Add(Tuple.Create(entry.Key, entry.Value.Item1));

            }

        }

​

        return result;

    }

}

​

// Helper class to store a pair of objects because Tuple's are immutable.

public class Pair<T1, T2> {

    public Pair(T1 t1, T2 t2) {

        Item1 = t1;

        Item2 = t2;

    }

​

    public T1 Item1 { get; set; }

    public T2 Item2 { get; set; }

}

​