Texas Instruments

Online Assessment
Online Assessment//Most Frequent N-Gram
Q1
Easy

Most Frequent N-Gram

StringsHash TableSliding Window
Set 1 • min
Problem Statement

The term N-gram refers to all possible substrings of length N formed using consecutive letters contained in a string. Given a string S and an integer N, find the most frequent N-gram and the number of times it appears in S.

If there is more than one N-gram with the same maximum frequency, print the first one that appears in S.

Input Format
  • ▸A single line of input contains string S and integer N separated by a single white space.
Output Format
  • ▸The output contains a string denoting the most frequent N-gram and an integer denoting the number of times the N-gram appears in S, separated by a single white space.
Constraints
  • 1 <= |S| <= 100
  • 1 <= N <= 10
  • N <= |S|
Sample Test Cases
Example 1
Input
banana 3
Output
ana 2
Explanation

The string S is 'banana' and N = 3.

All the 3-grams and their frequencies are:

- 'ban': 1

- 'ana': 2 (at indices 1..3 and 3..5)

- 'nan': 1

The most frequent 3-gram is 'ana' with frequency 2.

Example 2
Input
isamohanaismohana 3
Output
moh 2
Explanation

The 3-grams appearing with max frequency 2 include 'moh', 'oha', 'han', and 'ana'. 'moh' appears first in S (starting at index 3), so 'moh 2' is printed.

Expected Approach

1. Iterate through string S from index 0 to |S| - N. 2. Extract each substring `sub = S.substr(i, N)`. 3. Count occurrences using a hash map `freq[sub]` and track the first occurrence index `firstSeen[sub] = i`. 4. Find the substring with maximum frequency. If frequencies tie, pick the one with the smallest first occurrence index. 5. Print `<ngram> <frequency>`.