DEV Community

dev.to staff
dev.to staff

Posted on

Daily Challenge #304 - Consecutive Letters

#challenge

In this challenge, we will check if a string contains consecutive letters as they appear in the English alphabet and if each letter occurs only once.

Rules are: (1) the letters are adjacent in the English alphabet, and (2) each letter occurs only once.

For example:
solve("abc") = True, because it contains a,b,c
solve("abd") = False, because a, b, d are not consecutive/adjacent in the alphabet, and c is missing.
solve("dabc") = True, because it contains a, b, c, d
solve("abbc") = False, because b does not occur once.
solve("v") = True
All inputs will be lowercase letters.

Tests

solve("abc")
solve("zyx")
solve("azj")

Good luck!

This challenge comes from KenKemau 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 yo+challenge@dev.to with your suggestions!

Top comments (12)

Collapse
 
_bkeren profile image
'' •

JS

const solve = (string) =>
  string
    .split("")
    .sort()
    .map((i) => i.charCodeAt())
    .every(
      (element, index, array) =>
        index === 0 || array[index] - array[index - 1] === 1
    );
Enter fullscreen mode Exit fullscreen mode
Collapse
 
willsmart profile image
willsmart • • Edited

It's always nice to avoid a second iteration over elements if possible and efficient. This could allow a function to be applied on a stream/very-large-string, makes analysis of it easier, and just avoids having it do unnecessary work on elements it doesn't strictly need to deal with.
Here's a single loop TS implementation that will early exit as soon as it finds an element that...

  • has been seen before, or...
  • makes the new max char code too distant from the new min char code

If the whole string has been covered and the call to every didn't early exit, then all letters must be distinct (rule two covered), and the max code minus the min code must be less than the length of the string (they're all different to each other so this bound means they must be adjacent, rule one covered)

const solve = (s: string): boolean => {
  let minCode = Infinity,
    maxCode = -Infinity,
    seenChars = new Set<string>(),
    code: number;
  return [...s].every(
    c =>
      !seenChars.has(c) &&
      (
        seenChars.add(c),
        (code = c.charCodeAt(0)),
        (minCode = Math.min(code, minCode)),
        (maxCode = Math.max(code, maxCode)),
        maxCode - minCode < s.length
      )
  );
};
Enter fullscreen mode Exit fullscreen mode

Tested in kata

Edit: refactor to get rid of that sneaky arrayifying spread operator...

const solve = (s:string): boolean => {
  let minCode = Infinity,
    maxCode = -Infinity,
    seenChars = new Set<string>();
  for (const c of s) {
      if (seenChars.has(c)) return false;
      seenChars.add(c);
      const code = c.charCodeAt(0);
      minCode = Math.min(code, minCode);
      maxCode = Math.max(code, maxCode);
      if (maxCode - minCode >= s.length) return false;
  }
  return true;
};
Enter fullscreen mode Exit fullscreen mode
Collapse
 
bugb profile image
bugb • • Edited

It's always nice to avoid a second iteration

We also have space complexity

  • if 2 loops O(2n) and the space is O(1) then it still good to give a try
  • if you have only one loop but the space is O(n) or O(n^2), you should consider to use then ;)
Collapse
 
willsmart profile image
willsmart • • Edited

You're right, space is part of the equation too. It's all about what tradeoffs you're happy to make.

In this case, we're checking for duplicates in the string so we're either storing a memo hash (O(n) on space) or iterating over the pairs of elements (O(n^2) on time).
This one is O(n) on space and time, but you could defn make a fn that was O(1) on space if you were ok with O(n^2) on time.

(O(n) == O(2n) btw. The notation includes a multiplier to cover differences in the base case. So the top function up there where [...s] implicitly loops through the string before even hitting the every, actually has the same complexity as the lower function that is genuinely just one loop.)

Collapse
 
qm3ster profile image
Mihail Malo • • Edited

JavaScript

Efficient (for small strings)

works because if there are as many distinct characters as the length, there can't be duplicates

const solve = str => {
  const len = str.length
  let v = str.charCodeAt()
  for (let i = 1; i < len; i++) if (str.charCodeAt(i) < v) v = str.charCodeAt(i)
  for (let i = 0; i < len; i++) if (!str.includes(String.fromCharCode(v++))) return false
  return true
}
Enter fullscreen mode Exit fullscreen mode

TextEncoder 

const enc = new TextEncoder('ascii')
const solve = str => {
  const buf = enc.encode(str)
  const len = buf.length
  buf.sort()
  let v = buf[0]
  for (let i = 1; i < len; i++) if (buf[i] !== ++v) return false
  return true
}
Enter fullscreen mode Exit fullscreen mode

TextEncoder but without sorting 

const enc = new TextEncoder('ascii')
const solve = str => {
  const buf = enc.encode(str)
  const len = buf.length
  let v = buf.reduce(Math.min)
  for (let i = 0; i < len; i++) (buf.includes(v++)) return false
  return true
}
Enter fullscreen mode Exit fullscreen mode

TextEncoder without mutation 

const enc = new TextEncoder('ascii')
const solve = str => {
  const buf = enc.encode(str)
  buf.sort()
  return !!buf.reduce((a, x) => x - a === 1 ? x : 0)
}
Enter fullscreen mode Exit fullscreen mode

TextEncoder but finally a oneliner 

const solve = str => !!new TextEncoder('ascii')
  .encode(str)
  .sort()
  .reduce((a, x) => x - a === 1 ? x : 0)
Enter fullscreen mode Exit fullscreen mode
Collapse
 
jehielmartinez profile image
Jehiel Martinez • 
function solve (str) {
  let state = false
  const sorted = str
   .split('')
   .map(char => char.charCodeAt())
   .sort()

   sorted.every((char, index) => {
    if(char + 1 === exp[index+1]){
      state = true
    }
  })

  return state
}
Enter fullscreen mode Exit fullscreen mode
Collapse
 
edh_developer profile image
edh_developer • • Edited

Bitflags in Go

func solve(testString string) bool {
    bitFlags := 0
    characters := []rune(testString)

    for _, r := range characters {
        bitFlags |= 1 << (r - 97) // rune('a') == 97
    }

    for (bitFlags & 1) == 0 {
        bitFlags >>= 1
    }

    return bitFlags == (1<<len(testString) - 1)
}
Enter fullscreen mode Exit fullscreen mode
Collapse
 
sabbin profile image
Sabin Pandelovitch • • Edited

Javascript with less complexity

function solve(str) {
  let status = true;
  let counter = 1;
  while (status && counter < str.length) {
    status = str.charCodeAt(counter) === str.charCodeAt(counter-1)+1;
    counter++;
  }
  return status;
}
Enter fullscreen mode Exit fullscreen mode
Collapse
 
agtoever profile image
agtoever •

Not too elegant, but a compact and efficient one-liner, using Python 3.8's assignment expressions.

solve = lambda s: (ord_list := list(map(ord, s))) and max(ord_list) - min(ord_list) == len(s) - 1

for case in ['abc', 'abd', 'dabc', 'abbc', 'v', 'zyx', 'azj']:
    print(f'{case}: {solve(case)}')
Enter fullscreen mode Exit fullscreen mode

Try it online!

Collapse
 
cipharius profile image
Valts Liepiņš •

Solution in Haskell with O(n) time complexity:

import Data.Char (ord)
import qualified Data.IntMap.Strict as IMap

solve :: String -> Bool
solve = isUniqConsecutive . toCharMap
  where
    toCharMap = IMap.fromListWith (+) . map (flip (,) 1 . ord)
    isUniqConsecutive map
      = isUniq (IMap.elems map)
      && isConsecutive (IMap.keys map)
    isUniq = (== 1) . maximum
    isConsecutive [_] = True
    isConsecutive xs  = and $ zipWith (==) xs (pred <$> tail xs)
Enter fullscreen mode Exit fullscreen mode
Collapse
 
peter279k profile image
peter279k •

Here is the simple solution in Python:

def solve(st):
    arr = list(st)
    arr.sort()

    letters = 'abcdefghijklmnopqrstuvwxyz'

    return letters.count(''.join(arr)) >= 1
Enter fullscreen mode Exit fullscreen mode
Collapse
 
bugb profile image
bugb • • Edited

JS one line

solve=(s,A=[...s].sort(),c='charCodeAt')=>A.every((_,i)=>!i||A[i][c]()-A[i-1][c]()==1)
Enter fullscreen mode Exit fullscreen mode
View full discussion (12 comments)

Read next

mohitgoyal1108 profile image

Enhance Your WordPress Site’s Security with the Security Header Plugin by Inspired Monks

Mohit Goyal -

gaundergod profile image

My minimal VS Code setup for Vue, Typescript, Tailwind CSS, etc

Gleb Kotovsky -

mfyz profile image

Hosting my hobby projects from cheap HP mini desktop from my closet (Verizon Fios)

Fatih Felix Yildiz -

toshiya_matsumoto_ac94abe profile image

Method Chain: filter().map() is inefficient?

Toshiya Matsumoto -