Max Substring Occurrences

Moderate

0/80

0 upvote

Asked in company

Problem statement

You are given an array of strings, arr, containing N strings, and a non-empty target substring, target. Your task is to find and return the string from the array that contains the highest number of occurrences of the target substring.

There are two important rules to consider:

1) Overlapping Occurrences: The occurrences of target within a string are allowed to overlap. For example, if target is "aba", the string "ababa" contains two occurrences of the target: one starting at index 0 and another starting at index 2.

2) Tie-breaking: If two or more strings have the same maximum number of occurrences, you must return the one that appears first in the input array.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line contains a single integer N, the number of strings in the array.

The second line contains the target substring.

The next N lines each contain one string from the arr array.

Output Format:

Print a single line containing the string from the array that has the maximum number of occurrences of the target, according to the rules.

Note:

A simple approach using a split() function on the target string may not work correctly due to the overlapping rule. A more robust method is to iteratively search for the substring from the position immediately after the last found match.

Sample Input 1:

3
ap
apple
banana
apricot

Sample Output 1:

apple

Explanation for Sample 1:

"apple" contains "ap" 1 time.
"banana" contains "ap" 0 times.
"apricot" contains "ap" 1 time.
There is a tie between "apple" and "apricot". According to the tie-breaking rule, the one that appeared first, "apple", is returned.

Sample Input 2:

2
aba
ababa
abab

Sample Output 2:

ababa

Explanation for Sample 2:

"ababa" contains "aba" 2 times (at index 0 and 2).
"abab" contains "aba" 1 time (at index 0).
"ababa" has the clear maximum number of occurrences.

Expected Time Complexity:

The expected time complexity is O(N^3).

Constraints:

1 <= N <= 1000
1 <= length of each string in arr <= 1000
1 <= length of target <= 1000
All strings consist of lowercase English letters.

Time limit: 1 sec

Approaches (1)

Approach 1

Time Complexity

Space Complexity

(100% EXP penalty)

Max Substring Occurrences

Console