Problem Brief

Tiktok Viral Challenge

INTERNOA

See Tiktok online assessment and hiring insights

In the competitive world of social media, especially on platforms like TikTok, creators are constantly battling to produce viral content. The stakes are high—every video segment counts. As a data analyst working for TikTok, you've been tasked with a critical mission: to help creators optimize their videos by identifying the most promising segments that could lead to viral success.

Each segment of a TikTok video has an engagement attribute, which reflects its potential to go viral. This attribute is represented as an integer array engagementArray of size 26, corresponding to the letters of the alphabet ('a' to 'z'). Each element in this array is either '1' (indicating a viral segment) or '0' (indicating a non-viral segment).

The goal is to count all possible viral content combinations. A TikTok video is considered viral if the number of non-viral segments in any substring of the video does not exceed a given threshold k. The video is represented by a string of length n.

Given:

A string video of length n.

An integer k, the maximum allowed number of non-viral segments in a viral TikTok video.

An integer array engagementArray of size 26, where each element is either '1' (viral) or '0' (non-viral).

Find the number of unique non-empty substrings of the video that qualify as viral content.

Function Description

Complete the function countViralCombinations in the editor below.

countViralCombinations has the following parameter(s):

string video: A string representing the lineup of TikTok segments, where each character corresponds to a segment's unique attribute or engagement level.

int engagementArray[n]: An array of integers where each element is either '1' (indicating a viral segment) or '0' (indicating a non-viral segment). This array aligns with the English alphabet; for instance, 'a' corresponds to the first element.

int k: An integer denoting the maximum number of non-viral segments allowed in any content formation to consider it viral.

Returns

int: an integer denoting the number of unique content formations that meet the criteria of having no more than k non-viral segments, ensuring each formation is considered viral.

1Example 1

Input

video = "abc", engagementArray = [0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], k = 2

Output

Explanation

Open to discussion - In the description "int k: An integer denoting the maximum number of non-viral segments allowed in any content formation to consider it viral." means that non-viral should be <= than K. On the ss below, "abc" has 2(k) non-viral segmnets, so it should be considered viral instead of non-viral. So the ans should be 6 istead of 5. 🍓 Credit to aikay 🍓

2Example 2

Input

video = "stream", engagementArray = [0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], k = 2

Output

Explanation

n/a

3Example 3

Input

video = "stream", engagementArray = [0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], k = 2

Output

Explanation

n/a

Constraints

Limits and guarantees your solution can rely on.

1 ≤ n ≤ 1500.

1 ≤ k ≤ n.

engagementArray[i] ∈ {0, 1}