Daily Challenge #159 - Isogram

An isogram is a word that has no repeating letters, consecutive or non-consecutive. Implement a function that determines whether a string that contains only letters is an isogram. Assume the empty string is an isogram. Ignore letter case.

Example:
is_isogram("Dermatoglyphics" ) == true
is_isogram("aba" ) == false
is_isogram("moOse" ) == false # -- ignore letter case

---

This challenge comes from chunjef on CodeWars. Thank you to CodeWars, who has licensed redistribution of this challenge under the 2-Clause BSD License!

Want to propose a challenge idea for a future post? Email [e-mail] with your suggestions!

Comments

[Sam Watts]

Here’s my JS implementation using .reduce() :) :

 const isIsogram = word => {
  word = word.toLowerCase().split(“”)
  const result = word.reduce((accum, letter) => {
    !accum.includes(letter) && accum.push(letter);
    return accum;
  }, []);
  return result.length === word.length;
}

[Sam Watts]

Hindsight, @savagepixie ’s answer using sets was much better and more efficient! Set theory is always better in situations like this :)

[SavagePixie]

To be fair, Set usually isn't my first thought when solving problems. It's one of those things I kinda know are there but don't use that often.

[May Meow]

In php it can be done like this:

function is_isogram($str) {
    $str = strtolower($str);
    $maxRepeatingCount = 1;

    foreach (count_chars($str, 1) as $char => $value) {
        if ($value > $maxRepeatingCount) $maxRepeatingCount = $value;
     }

     if ($maxRepeatingCount == 1) return true;

     return false;
}

[Roberto B.]

I dropped some lines in Typescript.
Solution based on filter() and indexOf. indexOf returns the index of the first occurrence of the item in the array. So if a character appears the second time in the string, indexOf and index will be different.

function is_isogram(s: string): boolean {
    let a = s.toLowerCase().split("")
    return a.filter((char, index) => a.indexOf(char) !== index).length === 0
}

console.log("Dermatoglyphics:", is_isogram("Dermatoglyphics"))
console.log("aba:", is_isogram("aba"))
console.log("moOse:", is_isogram("moOse"))

[Rafael Acioly]

Python solution 🐍

from collections import Counter

def is_isogram(word: str) -> bool:
  letters = Counter(word.lower())
  letter, quantity = letters.most_common(1)[0]

  return quantity <= 1

[Craig McIlwrath]

Haskell

import Data.Char (toLower)

noDuplicates :: (Eq a) => [a] -> Bool
noDuplicates [] = True
noDuplicates (x:xs) = not (x `elem` xs) && noDuplicates xs

isIsogram :: String -> Bool
isIsogram = noDuplicates . map toLower

I think the complexity of this method is O(n^2), but it shouldn't matter too much since the since && can exit early, so the maximum number of iterations can only be 26 (by the pigeonhole principle).

[Vaibhav Yadav]

In Go.

func isIsogram(word string) bool {
    str := strings.ToLower(word)
    m := make(map[byte]bool)

    for i := 0; i < len(str); i++ {
        if m[str[i]] == true {
            return false
        }

        m[str[i]] = true
    }

    return true
}

[SavagePixie]

JavaScript

const isogram = str => new Set(str.toLowerCase().split('')).length === str.length

I think.

[zack]

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

[Amin]

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 strict";

function isIsogram(word) {
    const length = word.length;

    for (let current = 0; current < length; current++) {
        for (let next = current + 1; next < length; next++) {
            if (word[current].toLowerCase() === word[next].toLowerCase()) {
                return false;
            }
        }
    }

    return true;
}

console.log(isIsogram("Dermatoglyphics")); // true
console.log(isIsogram("aba")); // false
console.log(isIsogram("moOse")); // false
console.log(isIsogram("abcb")); // false

[zack]

So probably we can put all characters into Set then compare number of count. That is might be good solution.

[Ilyes Chouia]

in PHP

// Simple function to detect isogram words in PHP 

function is_isogram($s) 
{
    $s = strtolower($s);
    return count(array_unique(str_split($s, 1))) == strlen($s);
}

[Vaibhav Yadav]

Thanks for the suggestion.
Edited the solution.

[Nick Holmes]

Nice. Just the kind of "essential" solution I like.