3 ms·
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
by MaximumYComb 7y ago
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.
- thaumasiotes 7y ago> EDIT: The solution is actually incorrect so this is now semantics. Interesting use of "semantics". The question of "how fast does this algorithm run?" is totally independent from the question of "what does this algorithm do?"; the second one is semantic but you're discussing the first here.
- MaximumYComb 7y agoThe algorithm I described was O(n), you said it was O(3). I'm assuming this happened because my algorithm was actually an incorrect solution but you subconsciously added in steps to make it a correct algorithm which changed its complexity. Hence it's semantics because we seem to be discussing two different algorithms.