using System;

using System.Collections.Generic;

using System.Linq;

​

public class Program

{

    public static void Main()

    {

        var patterns = FindRepeatedPatterns("zf3kabxcde224lkzf3mabxc51+crsdtzf3nab=", 3);

​

        // Various test cases and values below

        //var patterns = FindRepeatedPatterns("abcabcABC", 3);

        //var patterns = FindRepeatedPatterns("aaaa", 3);

        //var patterns = FindRepeatedPatterns("bbbbb", 1);

        //var patterns = FindRepeatedPatterns("abcabc", 0);

        //var patterns = FindRepeatedPatterns(null, 3);

        //var patterns = FindRepeatedPatterns(null, 0);

​

        foreach (var pattern in patterns)

        {

            Console.WriteLine($"'{pattern.Key}' appears {pattern.Value} times");

        }

    }

​

    // Complexity:

    //      Time Complexity - O(n^2) because this method must loop through the input string once, then loop through unique patterns that were found

    //      Space Complexity - O(n) because this method stores a dictionary of pattern values dependent on method inputs

    //

    //      assumption: patternLength will be a non-nullable integer

    /// <summary>

    /// Search <paramref name="input"/> for repeated patterns that are of <paramref name="patternLength"/> length

    /// </summary>

    /// <param name="input"></param>

    /// <param name="patternLength"></param>

    /// <returns>An <c>IEnumerable</c> of <c>KeyValuePairs</c> that contains the pattern as the key and the occurrence count as the value</returns>

    public static IEnumerable<KeyValuePair<string, int>> FindRepeatedPatterns(string input, int patternLength)

    {

        var patterns = new Dictionary<string, int>();

​

        // check for valid input and patternLength. if input length is shorter than or equal to patternLength

        // return empty pattern list, since there can't be a repeated pattern of patternLength in the input

        //

        // assumption: we want to return zero pattern matches (an empty list) on invalid inputs, rather than throw an error

        if (string.IsNullOrWhiteSpace(input) || 

            patternLength <= 0 || 

            input.Length <= patternLength)

        {

            return patterns.ToList();

        }

​

        // iterate through input, finding all patterns of patternLength length

        //

        // assumption: the pattern search does not loop through the string

        for (int i = 0; i <= input.Length - patternLength; i++)

        {

            var pattern = input.Substring(i, patternLength);

​

            // increment the current occurrence count for this pattern in our Dictionary

            //

            // assumption: repeated patterns are case-sensitive, meaning abx != ABX

            patterns[pattern] = patterns.GetValueOrDefault(pattern) + 1;

        }

​

        // return only the patterns with an occurrence count greater than one

        return patterns.Where(pattern => pattern.Value > 1);

    }

}