Use 2 pointers i, j. i runs from left side of string and j runs from right side of string.
We will compare each element on left side with right size if equal we will return false the if not equal increase i and decrease j then continue compare. I came up with idea when i read the problem
I might be wrong, but if you try with the word abcb which is not a word but just for the simplicity of the explanation, it would fail to find it using two pointers.
abcb
i j continue
abcb
ij return true (but it's false here)
You have, in my understanding, no other choice but to check every letters for each letter pass, which make the worst case an O(n²) complexity. And I think the best case scenario for the complexity could be O(1) when the same letter is repeated twice in a row.
Here is what the algorithm could look like in JavaScript.
Use 2 pointers i, j. i runs from left side of string and j runs from right side of string.
We will compare each element on left side with right size if equal we will return false the if not equal increase i and decrease j then continue compare. I came up with idea when i read the problem
I might be wrong, but if you try with the word
abcb
which is not a word but just for the simplicity of the explanation, it would fail to find it using two pointers.You have, in my understanding, no other choice but to check every letters for each letter pass, which make the worst case an O(n²) complexity. And I think the best case scenario for the complexity could be O(1) when the same letter is repeated twice in a row.
Here is what the algorithm could look like in JavaScript.
So probably we can put all characters into Set then compare number of count. That is might be good solution.