Most Frequent k-length Substring

Given a DNA sequence represented as a string and an integer \(k\), your task is to determine the most frequent substring of length \(k\) within the sequence.

If there are multiple substrings that occur the same maximum number of times, output the one that is lexicographically smallest. In the lexicographical order, comparison is made in the natural order of characters (i.e., 'A' < 'C' < 'G' < 'T'). If the length of the sequence is less than \(k\), output an empty string.

Input is provided via standard input and output should be written to standard output.

inputFormat

The input consists of two lines:

• The first line contains the DNA sequence, a non-empty string.
• The second line contains an integer \(k\), representing the length of the substring.

outputFormat

Output the most frequent substring of length \(k\> to standard output. If the sequence length is less than \(k\), output an empty string.

ACGTACGTACGT
3

ACG