Check for repeated characters in a string Javascript

I was wondering if there is a way to check for repeated characters in a string without using double loop. Can this be done with recursion?

An example of the code using double loop (return true or false based on if there are repeated characters in a string):

var charRepeats = function(str) {
    for(var i = 0; i <= str.length; i++) {
        for(var j = i+1; j <= str.length; j++) {
            if(str[j] == str[i]) {
                return false;
            }
        }
    }
    return true;
}

Many thanks in advance!

Answers:

Answer

(A recursive solution can be found at the end, of this answer.)

You could use javascript builtin Array functions some MDN some reference

 var text = "test".split("");
 text.some(function(v,i,a){
   return a.lastIndexOf(v)!=i;
 });

callback parameters:
v current value of the iteration
i current index of the iteration
a current array

.split("") create an array from a string
.some(function(v,i,a){ ... }) goes through an array until the function returns true, and ends than right away. (doesn't loop through the whole array, if it finds an match earlier)

Details to the some function can be found here

Tests, with several strings:

var texts = ["test", "rest", "why", "puss"];


for(var idx in texts){
    var text = texts[idx].split("");
    document.write(text + " -> " + text.some(function(v,i,a){return a.lastIndexOf(v)!=i;}) +"<br/>");
    
  }
  //tested on win7 in chrome 46+

If recursion is needed.

Update for recursion:

//recursive function
function checkString(text,index){
    if((text.length - index)==0 ){ //stop condition
        return false; 
    }else{
        return checkString(text,index + 1) 
        || text.substr(0, index).indexOf(text[index])!=-1;
    }
}

// example Data to test
var texts = ["test", "rest", "why", "puss"];

for(var idx in texts){
    var txt = texts[idx];
    document.write( txt +  " ->" + checkString(txt,0) + "<br/>");
}
//tested on win7 in chrome 46+

Answer

This will do:

function isIsogram (str) {
    return !/(.).*\1/.test(str);
}
Answer

you can use .indexOf() and .lastIndexOf() to determine if an index is repeated. Meaning, if the first occurrence of the character is also the last occurrence, then you know it doesn't repeat. If not true, then it does repeat.

var example = 'hello';

var charRepeats = function(str) {
    for (var i=0; i<str.length; i++) {
      if ( str.indexOf(str[i]) !== str.lastIndexOf(str[i]) ) {
        return false; // repeats
      }
    }
  return true;
}

console.log( charRepeats(example) ); // 'false', because when it hits 'l', the indexOf and lastIndexOf are not the same.
Answer

The algorithm presented has a complexity of (1 + n - (1)) + (1 + n - (2)) + (1 + n - (3)) + ... + (1 + n - (n-1)) = (n-1)*(1 + n) - (n)(n-1)/2 = (n^2 + n - 2)/2 which is O(n2).

So it would be better to use an object to map and remember the characters to check for uniqueness or duplicates. Assuming a maximum data size for each character, this process will be an O(n) algorithm.

function charUnique(s) {
  var r = {}, i, x;
  for (i=0; i<s.length; i++) {
    x = s[i];
    if (r[x])
      return false;
    r[x] = true;
  }
  return true;
}

On a tiny test case, the function indeed runs a few times faster.

Note that JavaScript strings are defined as sequences of 16-bit unsigned integer values. http://bclary.com/2004/11/07/#a-4.3.16

Hence, we can still implement the same basic algorithm but using a much quicker array lookup rather than an object lookup. The result is approximately 100 times faster now.

var charRepeats = function(str) {
  for (var i = 0; i <= str.length; i++) {
    for (var j = i + 1; j <= str.length; j++) {
      if (str[j] == str[i]) {
        return false;
      }
    }
  }
  return true;
}

function charUnique(s) {
  var r = {},
    i, x;
  for (i = 0; i < s.length; i++) {
    x = s[i];
    if (r[x])
      return false;
    r[x] = true;
  }
  return true;
}

function charUnique2(s) {
  var r = {},
    i, x;
  for (i = s.length - 1; i > -1; i--) {
    x = s[i];
    if (r[x])
      return false;
    r[x] = true;
  }
  return true;
}

function charCodeUnique(s) {
  var r = [],
    i, x;
  for (i = s.length - 1; i > -1; i--) {
    x = s.charCodeAt(i);
    if (r[x])
      return false;
    r[x] = true;
  }
  return true;
}

function regExpWay(s) {
  return /(.).*\1/.test(s);
}


function timer(f) {
  var i;
  var t0;

  var string = [];
  for (i = 32; i < 127; i++)
    string[string.length] = String.fromCharCode(i);
  string = string.join('');
  t0 = new Date();
  for (i = 0; i < 10000; i++)
    f(string);
  return (new Date()) - t0;
}

document.write('O(n^2) = ',
  timer(charRepeats), ';<br>O(n) = ',
  timer(charUnique), ';<br>optimized O(n) = ',
  timer(charUnique2), ';<br>more optimized O(n) = ',
  timer(charCodeUnique), ';<br>regular expression way = ',
  timer(regExpWay));

Answer
function chkRepeat(word) {
    var wordLower = word.toLowerCase();
    var wordSet = new Set(wordLower);
    var lenWord = wordLower.length;
    var lenWordSet =wordSet.size;

    if (lenWord === lenWordSet) {
        return "false"
    } else {
        return'true'
    }
}
Answer

Another way of doing it using lodash

var _ = require("lodash");
var inputString = "HelLoo world!"
var checkRepeatition = function(inputString) {
  let unique = _.uniq(inputString).join('');
  if(inputString.length !== unique.length) {
    return true; //duplicate characters present!
  }
  return false;
};
console.log(checkRepeatition(inputString.toLowerCase()));
Answer

You can use "Set object"!

The Set object lets you store unique values of any type, whether primitive values or object references. It has some methods to add or to check if a property exist in the object.

Read more about Sets at MDN

Here how i use it:

 function isIsogram(str){
  let obj = new Set();

  for(let i = 0; i < str.length; i++){
    if(obj.has(str[i])){
      return false
    }else{
      obj.add(str[i])
    }
  }
  return true
}

isIsogram("Dermatoglyphics") // true
isIsogram("aba")// false

Tags

Recent Questions

Top Questions

Home Tags Terms of Service Privacy Policy DMCA Contact Us

©2020 All rights reserved.