Elly is playing Scrabble with her family. The exact rules of the game are not important for this problem. You only need to know that Elly has a holder that contains a row of N tiles, and that there is a single letter on each of those tiles. (Tiles are small square pieces of wood. A holder is a tiny wooden shelf with room for precisely N tiles placed in a row.)… [More...]

As many others I came up with a simple greedy heuristic. We can simply find the characters one by one starting from the left. Suppose we want to find the i-th character. We just look at **maxDistance** characters on the left and ** maxDistance **on the right and we take the

*smallest*letter. We loop through all the letters and we get the whole sequence.

There are however two caveats. First, we need to make sure that we use all letters. Imagine **maxDistance = 2 **and letters **ZAAA. **With the algorithm described above we have a problem while choosing the last character. Lets look what happens

- Iteration 1: Candidates
**ZAA**, we choose**A**, the string so far is just**A** - Iteration 2: Candidates
**ZAA**(one A is gone), we choose**A**, the string so far is just**AA** - Iteration 3: Candidates
**ZA**(two As are gone), we choose**A**, the string so far is just**AAA** - Iteration 4: ERROR! We ran out of candidates!

To avoid this situation we simply need to use the first character of the list when it is the last chance to use it. Then the last to iterations are

- Iteration 3: Candidates
**ZA**(two As are gone), we must choose**Z**, the string so far is just**AAZ** - Iteration 4: Candidates
**A**, we choose**A**, the string so far is just**AAZA**

The second caveat is that, whenever there is more than one smallest letter than we take the one from the left. This will give us more possibilities later on.

It’s quite easy to prove that this strategy gives the optimal solution.

My sub-optimal and sub-pretty Java

import java.util.Arrays; public class EllysScrabble { public String getMin(String letters, int maxDistance) { StringBuilder newstring = new StringBuilder(letters); StringBuilder oldstring = new StringBuilder(letters); for (int i = 0; i < letters.length(); i++){ int start = Math.max(i - maxDistance, 0); int end = Math.min(i + maxDistance + 1, letters.length()); char[] candidates = new char[end - start]; oldstring.getChars(start, end, candidates, 0); if ((start == i - maxDistance) && candidates[0] != '['){ newstring.setCharAt(i, candidates[0]); continue; } Arrays.sort(candidates); newstring.setCharAt(i, candidates[0]); for (int j = start; j < end; j++){ if (oldstring.charAt(j) == candidates[0]){ oldstring.setCharAt(j, '['); break; } } } return newstring.toString(); } }