/*

Some notes/thoughts/observations:

​

Since this is a DB developer position, I created a SQL solution.

​

To avoid the "does not follow instructions" label, I also created a C# solution.

​

The basic algorithm is to go through the input string once from the beginning.  Take each possible pattern of

the given length and add it to a table or list with an occurence count of 1, unless it has already been added,

in which case, increment the occurence count.  This searches through the string only once, but it searches

the table/list once per pattern.

​

Input validation was not specified.  I chose to have invalid inputs (negative pattern length,

pattern length >= input string length) return no results found.

​

Since "input" maximum length was not specified, I used VARCHAR(MAX) as the data type.  This might cause

some performance issues, since that data type can not be part of a PK.  So the search of the table

variable will always be a table scan.  Probably not an issue unless the input string is VERY large.

​

Depending on what collation SQL is using, certain unexpected results may occur.  For instance,

SQL is usually defined as case insensitive.  If that is true, patterns 'abc' = 'ABC' = 'Abc' etc.

These would be returned as multiple occurences of the same pattern.

​

Output order was not defined, so patterns will be returned in the order in which they were found.

​

In the example, the pattern 'bxc' also appears twice.

​

I looked at other algorithms that would take the first pattern, then search the rest of the string

for occurences of that pattern.  But I figured I would have to store the results for multiple occurences

anyway and check against that for every subsequent pattern.  And the code would search through the

input string once for every new pattern encountered (albeit a shortened string).  That would be much

more difficult in SQL, but definitely manageable in C#.  Regardless, I can think of only a few

instances where that would perform better than the algorithm above.

*/

​

/* SQL Solution:

​

DROP PROCEDURE IF EXISTS dbo.RepeatPatternLst;

GO

​

CREATE PROCEDURE dbo.RepeatPatternLst

(

    @pSearchString          VARCHAR(MAX),

    @pPatternLength         INT

)

AS

BEGIN

-----------------------------------------------------------------------------------------------

-- Procedure Name:  RepeatPatternLst

-- Description:     Return patterns of length @pPatternLength in @pSearchString that occur more than once

-- 

-- Created By:      smataka

-- Date Created:    2021-12-29

--

-- CHANGE LOG **

-- Changed By   Date        Description

-- smataka      2021-12-29  Created 

-----------------------------------------------------------------------------------------------

​

-- Declare variables

    -- procedure variables

    DECLARE

        @StringLength       INT = LEN(@pSearchString),

        @StringPosition     INT = 1,

        @Pattern            VARCHAR(MAX),

        @RowCnt             INT;

​

    -- output table

    DECLARE

        @ResultTbl  TABLE

        (

            Pattern         VARCHAR(MAX)    NOT NULL,

            PatternCnt      INT             NOT NULL

        );

​

-- Find patterns in @pSearchString

    -- only process valid input:

        -- PatternLength should be positive

        -- PatternLength should be less than the length of the input string

    IF ( ( @pPatternLength > 0 ) AND ( @pPatternLength < @StringLength ) )

    BEGIN

        WHILE ( @StringPosition <= ( @StringLength - @pPatternLength + 1 ) )

        BEGIN

            -- Get the current pattern

            SELECT

                @Pattern = SUBSTRING(@pSearchString, @StringPosition, @pPatternLength);

​

            -- If the pattern was found previously, increase the count

            -- note, this will update zero records if this pattern is new

            UPDATE r

            SET

                r.PatternCnt = r.PatternCnt + 1

            FROM @ResultTbl AS r

            WHERE r.Pattern = @Pattern;

​

            SELECT

                @RowCnt = @@ROWCOUNT;

​

            -- If the pattern is new, insert with count of 1

            IF ( @RowCnt = 0 )

            BEGIN

                INSERT @ResultTbl

                (

                    Pattern,

                    PatternCnt

                )

                SELECT

                    @Pattern AS Pattern,

                    1 AS PatternCnt;

            END

​

            -- Move to next position

            SELECT

                @StringPosition = @StringPosition + 1;

        END

    END

​

-- output results, returning patterns that occur more than once

    SELECT

        r.Pattern,

        r.PatternCnt

    FROM @ResultTbl AS r

    WHERE r.PatternCnt > 1;

​

    RETURN (0);

END;

GO

​

​

EXEC dbo.RepeatPatternLst @pSearchString = 'zf3kabxcde224lkzf3mabxc51+crsdtzf3nab=', @pPatternLength = 3;

GO

*/

​

using System;

using System.Collections.Generic;

public class Program

{

    static void RepeatPatternLst(string SearchString, int PatternLength)

    {

        // function variables

        int StringLength = SearchString.Length;

        int StringPosition = 0;

        string PatternCurrent;

        int PatternArrayIndex;

​

        // output arrays

        var Pattern = new List<string>();

        var PatternCnt = new List<int>();

​

        // Find patterns in SearchString

        // only process valid input:

        // PatternLength should be positive

        // PatternLength should be less than the length of the input string

        if ( PatternLength > 0 && PatternLength < StringLength )

        {

            while ( StringPosition <= ( StringLength - PatternLength ) )

            {

                // get the current pattern

                PatternCurrent = SearchString.Substring(StringPosition, PatternLength);

​

                // check to see if we have already found the curent pattern

                PatternArrayIndex = Pattern.IndexOf(PatternCurrent);

​

                // if the pattern is new, add it to the output arrays

                if ( PatternArrayIndex == -1 )

                {

                    Pattern.Add(PatternCurrent);

                    PatternCnt.Add(1);

                }

                // otherwise, increment the number of occurences

                else

                {

                    PatternCnt[PatternArrayIndex]++;

                }

​

                StringPosition++;

            }

        }

​

        // output the results, returning patterns that occur more than once

        for (int i = 0; i < PatternCnt.Count; i++)

        {

            if ( PatternCnt[i] > 1 )

            {

                Console.WriteLine("Repeated Pattern: " + Pattern[i] + " Pattern Count: " + PatternCnt[i].ToString());

            }

        }

​

        return;

    }

​

    public static void Main()

    {

        RepeatPatternLst("zf3kabxcde224lkzf3mabxc51+crsdtzf3nab=", 3);

    }

}