Question 1: You are working on developing a movie with Amazon Video and want to devise an application to easily break up individual shots in a video into scenes.

There is already an algorithm that breaks the video up into shots (short sequences from a particular camera angle) and labels them.

Write a function which will partition a sequence of labels into minimal subsequences so that no labels appear in more than one subsequence.

The output should be the length of each subsequence.

Input:

The input to the function/method consists of an argument - inputList, a list of characters representing the sequence of shots.

Output:

Return a list of integers representing the length of each scene, in the order in which it appears in the given sequence of shots.

Example:

- Input:

inputList = [a,b,a,b,c,b,a,c,a,d,e,f,e,g,d,e,h,i,j,h,k,l,i,j] - Output:

[9, 7, 8]

Explanation:

The correct partitioning is:

a,b,a,b,c,b,a,c,a,/d,e,f,e,g,d,e,/h,i,j,h,k,l,i,j

To ensure that no label appears in more than one subsequence, subsequences are as small as possible, and subsequences partition the sequence.

The length of these subsequences are 9, 7 and 8.

Question 2: Michelle has created a word game for her students. The word game begins with Michelle writing a string and a number, K, on the board.

The students must find a substring of size K such that there is exactly one character that is repeated one;

in other words, there should be k - 1 distinct characters in the substring.

Write an algorithm to help the students find the correct answer. If no such substring can be found, return an empty list;

if multiple such substrings exist, return all them, without repetitions. The order in which the substrings are does not matter.

Input:

The input to the function/method consists of two arguments - inputString, representing the string written by the teacher;

num an integer representing the number, K, written by the teacher on the board.

Output:

Return a list of all substrings of inputString with K characters, that have k-1 distinct character i.e.

exactly one character is repeated, or an empty list if no such substring exist in inputString.

The order in which the substrings are returned does not matter.

Constraints:

The input integer can only be greater than or equal to 0 and less than or equal to 26 (0 <= num <= 26)

The input string consists of only lowercase alphabetic characters.

Example

Input:

inputString = awaglk

num = 4

Output:

[awag]

Explanation:

The substrings are {awag, wagl, aglk}

The answer is awag as it has 3 distinct characters in a string of size 4, and only one character is repeated twice.