### James S. Plank

Mon Sep 5 01:01:35 EDT 2016
It's an awkward problem writeup, but once you understand what the problem is asking, you can start to craft a solution. Here are two things that have to be true about x:
1. x[0] has to equal x.size(). This is because there have to be exactly N one-character strings, and x.size() is equal to N.
2. Suppose j is the largest value for which x[j] is greater than zero. Then there has to be a string with j consecutive characters, and there have to be two strings with j-1 consecutive characters, and three strings with j-2 consecutive characters, and so on.
So, here's an idea. Let's create a data structure S, which is a map of two integers. If S[j] = k, then the password will have k substrings of exactly j consecutive characters.

Let's do some examples:

• In Example 0, x = { 5, 0, 0, 0, 0 }. That means that S will be { [1,5] }.
• In example 1, x = { 4, 2, 1, 0 }. That means that S will be { [1,1], [3,1] }.
• In example 3, x = { 4, 3, 2, 1 }. That means that S will be { [4,1] }.
• Here's one that's not in the examples. Suppose x = { 7, 4, 2, 0, 0, 0, 0 }. Then there have to be two strings of three consecutive characters, and one of one character. S will be { [1,1], [3,2] }.
To create S, you need to find the largest value j such that x[j] is non-zero. Then you add one value to S[j], and you subtract one from x[j], two from x[j-1], three from x[j-2] and so on. If you get to a point where some value of x is negative, then you return "".

Keep doing this until every value of x is zero. Then your map S is done.

To create the password from S, you will start with S's largest key, and add that many a's. Then go to the smallest key, and add that many b's. Continue like that. For example, suppose that S is { [1,1], [2,1], [3,1], [4,1] }. Then the password will be "aaaabaaabb".

If S is { [1,1], [3,2] }, then the password will be "aaabaaa".

To reiterate, your steps here are:

• Create the map S from x, by finding the largest index j of x that is non-zero, adding an entry for S that corresponds j, and then subtracting from all of the x values that have indices less than or equal to j.
• From S, you create the password using the high values of S for the character 'a', and the low values for the character 'b'.