Business Technology Analyst

You have been given a string 'S' which only consists of lowercase English-Alphabet letters. Your task is to find the shortest (minimum length) substring from 'S' which contains all the characters of 'S' at least once.

Note:

If there are more than one substring with the shortest length, then find one which appears earlier in the string ‘S’ i.e. substring whose starting index is lowest.

For example:

If the given string ‘S’ = "abcba", then the possible substrings having all the characters of ‘S’ at least once and of minimum length are "abc" and "cba". 

As "abc" starts with a lower index (i.e. 0, "cba" starts with index 2), we will return the string "abc" as our shortest substring that contains all characters of 'S'.

Monk's favorite game is Football and his favorite club is "Manchester United". Manchester United has qualified for the Champions League Final which is to be held at the Wembley Stadium in London. So, he decided to go there and watch his favorite team play. After reaching the stadium, he saw that many people have lined up for the match tickets. He knows that there are 'M' rows in the stadium with different seating capacities. They may or may not be equal. The price of the ticket depends on the row. If the row has 'K' vacant seats, then the price of the ticket will be 'K' pounds. Now, every football fan standing in the line will get a ticket one by one.

You are given 'N' number of fans waiting for the tickets and seating capacities of different rows. The club wants to gain maximum pounds with the help of ticket sales.

Your task is to print the maximum possible pounds that the club will gain with the help of ticket sales.

A thief wants to loot houses. He knows the amount of money in each house. He cannot loot two consecutive houses. Find the maximum amount of money he can loot.