Find string in array of strings which has duplicated symbols

Question

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)

why are you using map? map is not used for looping. Your code does not exit when it finds a match — epascarello
– epascarello, Commented Aug 16, 2021 at 19:11
@epascarello just to get array items one by one. I thought it would be better than for loop in for loop — user14587589
– user14587589, Commented Aug 16, 2021 at 19:12

Spectric · Accepted Answer · 2021-08-16 19:23:02Z

3

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:

edited Aug 16, 2021 at 19:23

answered Aug 16, 2021 at 19:08

Spectric

32.6k6 gold badges32 silver badges56 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

user14587589 Over a year ago

So just make sure. We start filtering array of strings. Then I split each of them one by one and use new Set built-in js function to found the ones with duplicates?

Spectric Over a year ago

@user14587589 using the Set constructor gets the unique items in the array. If the original string only had unique characters, the result would not change, thus the strings would be equal in the end

user14587589 Over a year ago

What about the !=e part? could you explain please?

epascarello · Accepted Answer · 2021-08-16 21:07:45Z

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))

Collectives™ on Stack Overflow

Find string in array of strings which has duplicated symbols

2 Answers 2

3 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related