Ideal string

An ideal string is a string where the 1-based index of the first occurrence of each letter is equal to the number of occurrences of that letter in the string. For example, the "BAOOOA" is an ideal string (quotes for clarity only). The letter 'B' appears 1 time, and its index is 1. The letter 'A' occurs 2 times and its first index is 2. The letter 'O' occurs 3 times and its first index is 3.

Given an int length, return the lexicographically smallest ideal string of that length containing only uppercase letters ('A'-'Z'). If there are no such ideal strings of that length, return an empty String instead.

Source: TopCoder

Solution:
To solve this problem we need to come up with a formula which tells us whether it is possible to have such a string at all or not. As we can see that element at index 1 must appear once, index 2 must appear twice and index n must appear n times.

So total length of string = length = 1 + 2 + .... n
hence n*(n+1)/2 = length
We should be able to represent the length as above, if we cannot then empty string can be returned.
If we can represent we should do the following:
1. Find n from the above equation.
2. Fill "A" in the 1st index and fill the remainder(0) of "A" in the n+1 th index.
3. Fill "B" in the 2nd index and fill the remainder(1) of "B" in the index after the previous fill.
3. Fill "C" in the 3rd index and fill the remainder(2) of "C" in the index after the previous fill.
........
n. Fill "n" in the nth index and fill the remainder (n-1) of "n" in the index after previous fill

After the above operation is done, print the array.