The smallest greater and the shortest slice

The smallest greater

Our first task this week is as follows: You are given an array of characters (a..z) and a target character. Write a script to find out the smallest character in the given array lexicographically greater than the target character.

The best way to approach this seems to me to sort the array, and then look for the first character in the sorted array that follows the target character alphabetically. As the array is sorted this is bound to be the smallest such character.

This works for all of Mohammad's examples except the last, where the array is 't, g, a, l' and the target character is 'v'.  So I would say there is no answer, though Mohammad's example says the answer is 'v', which isn't in the array.

And the shortest slice

The second task says that we are given an array of two or more non-negative integers and are asked to write a script to find out the smallest slice of the array having the same degree as the array itself. We are told that the degree of an array is the maximum frequency of an element in the array.

It seems sensible to start by writing a subroutine to return the degree of an array.

We know that the slice can't be any shorter than the degree of the original array, so that's a good start. Let's begin at that size and work up, and then in an inner loop check every slice of that size, and then the next size up and so on until we find a slice with the same degree as the original array.

And that's what I did. There is a slight wrinkle, in that the answer may not be unique. For example 1, 1, 1, 2, 2, 2 has two slices - 1, 1, 1 and 2, 2, 2 - each of degree 3.  I chose to output all the slices meeting the criteria, so my inner (position) loop does not immediately terminate if it finds a solution, but it does stop the outer (size) loop from going further.