Problem Brief

Find Dominance

INTERNOA

See Amazon online assessment and hiring insights

In an Amazon content analysis project, there is a dataset of strings, each representing distinct attributes. The goal is to determine the dominance of the most influential attribute prefix for various lengths.

The dominance of a prefix, denoted as t, is measured by the number of instances in the dataset where t serves as a prefix. For example, in the dataset ["abab","ababc","abab"], the dominance of the prefix "ab" is 3, and the dominance of the prefix "aba" is 3.

The most influential prefix of a specific length len is identified as the prefix with the highest dominance among all strings of the same length. If there are multiple prefixes of the same length with equivalent dominance, any prefix from that set may be considered the most influential.

Formally, given the dataset s consisting of n strings, each of length m, the objective is to determine, for each prefix of length len ranging from 1 to m, the dominance of the most influential prefix of that length.

Function Description

Complete the function findDominance in the editor below.

findDominance has the following parameters:

string s[]: The array of strings

Returns

int[]: the dominance of the most influential prefix of lengths from 1 to m

Constraints

2 ≤ n ≤ 500
1 ≤ m ≤ 2000

🐳 1004 thanks to spike!👍 Truly grateful! 🌟

1Example 1

Input

s = ["aba", "abb", "aba"]

Output

[3, 3, 2]

Explanation

The most influential prefix of length 1 is "a" with a dominance of 3, the most influential prefix of length 2 is "ab" with a dominance of 3, and the most influential prefix of length 3 is "aba" with a dominance of 2, so the answer is [3, 3, 2] :)

2Example 2

Input

s = ["abc", "aaa", "aba"]

Output

[3, 2, 1]

Explanation

Constraints

Limits and guarantees your solution can rely on.

2 ≤ n ≤ 500
1 ≤ m ≤ 2000