I have an array of strings, And I want to find the ones which has duplicated symbols in them so far I have this:
const listOfStrings = ['aabbb','cccw','ad']
function findStringsWithDuplicates(arr) {
const finalResult = [];
arr.map(symbol => {
for(let i = 0;i < symbol.length - 1;i++) {
if(symbol[i] === symbol[i+1] && symbol[i] === symbol[i-1]) {
finalResult.push(symbol)
}
}
})
return finalResult;
}
findStringsWithDuplicates(listOfStrings) // [ 'aabbb', 'cccw' ]
It works as it should but I think that as an algorithm it is bad because as much I understand right now it is O(n) square by time complexity. Is there any way to make it just O(n)
You can split the string into an array of each individual character, then get the unique items in that array and join back together. This will return the original string with duplicate characters stripped out.
We then compare whether the result after joining is not equal to the original string or not. If it is equal, we know the string has no duplicates, since we just removed all duplicates. If it is not, we know it contains duplicates.
const listOfStrings = ['aabbb','cccw','ad']
function findStringsWithDuplicates(arr) {
const finalResult = arr.filter(e => [...new Set(e.split(''))].join('') != e)
return finalResult;
}
console.log(findStringsWithDuplicates(listOfStrings)) // [ 'aabbb', 'cccw' ]In the example above, e.split('') simply splits the string into an array of characters. [...new Set(arr)] gets the unique characters, and join('') joins the items of the array together. != then checks whether the result is not equal to the original string.
References:
I thought I would show you how to clean up your answer. Need to start one index greater than the first, since you are checking -1 in yours.
You should not use map unless you are making a new array from the contents of the array you are looping over.
If you use filter, you can get rid of the push and it will exit when you find a match, not keep checking.
const listOfStrings = ['aabbb', 'cccw', 'ad', "eeffgghhiiijj"]
function findStringsWithDuplicates(arr) {
// use filter instead of pushing to a new array
return arr.filter(string => {
// start loop at second index, end at second to last
for (let i = 1; i < string.length - 1; i += 1) {
// if we have three matches, then say it is good
if (string[i - 1] === string[i] && string[i + 1] === string[i]) return true;
}
// if we got here, we had no matches
return false;
});
}
console.log(findStringsWithDuplicates(listOfStrings))Can you make it a little faster? Not a huge improvement, but you are making a check so you can determined in the 2nd and 3rd is the same, if not you can skip it.
const listOfStrings = ['aabbb', 'cccw', 'ad', "eeffgghhiiijj"]
function findStringsWithDuplicates(arr) {
// use filter instead of pushing to a new array
return arr.filter(string => {
// start loop at second index, end at second to last
for (let i = 1; i < string.length - 1; i += 1) {
const middle = string[i];
const secondValid = string[i + 1] === middle;
const firstValid = secondValid && string[i - 1] === middle;
// if second match is not valid, we know next loop's iteration is not valid so jump it ahead
if (!secondValid) i++;
// see if we have a match, if we do exit with true
else if (firstValid && secondValid) return true;
}
// if we got here, we had no matches
return false;
});
}
console.log(findStringsWithDuplicates(listOfStrings))And this is another way to solve it with a counter
const listOfStrings = ['aabbb', 'cccw', 'ad', "eeffgghhiiijj"]
function findStringsWithDuplicates(arr) {
// use filter instead of pushing to a new array
return arr.filter(string => {
let current = string[0];
let count = 1;
let i = 1;
while (i < string.length) {
const next = string[i];
// is next letter the same?
if (current === next) {
// up the count
count++;
// if count is 3, exit out
if (count === 3) return true;
} else {
//reset back to new character
current = next;
count = 1;
}
// move to next
i++;
}
return false;
});
}
console.log(findStringsWithDuplicates(listOfStrings))