You only check each character in the string once. A hashmap can check if the char is used already.

For each char in the original string there is: * 1 check in hashmap (let's assume it was found). This is O(1) * build a new string where we remove that char from the string we are building (string2) and add it to the end. This step may look O(n) initially since we need to find that char in string2 but string2 is capped at 26 characters so it's O(1) * One comparison between the string we are building and the altered version.

How does that make it O(n^3)? I can't see which step inside the initial loop is O(n) or greater.

EDIT: The solution is actually incorrect so this is now semantics.