Coding Problems Part 2

This week I am going over some Javascript coding problems that I found rather challenging and learned a lot from working on.

Shortest Substring

Given a string input, find the shortest substring that has all of the unique letters of the string within it. For example, when given s = “dabbcabcd”, the 2 substrings would be “dabbc” and “abcd”. The shortest substring would be “abcd”.

function shortestSubstring(s) {
  if (s.length === 1) return s
  let words = []
  let stringCopy = s
  let length = stringCopy.length
  let arr = s.split("")
  let uniqueLetters = arr.filter((item, i, ar) => ar.indexOf(item) === i);
  while (length > 0) {
    let word = findStr(stringCopy, uniqueLetters)
    words.push(word)
    length -= word.length
    //removes substring from stringCopy
    stringCopy = s.replace(word, '')
  }
  let noShortWords = words.filter(word => !word.includes("*"))
  let shortestSubstring = noShortWords.reduce((a, b) => a.length <= b.length ? a : b)
  return shortestSubstring
}
function findStr(s, uniqueLetters) {
  let count = 0
  let indexes = []
  for (let x = 0; x < uniqueLetters.length; x++) {
    // checks for repeated characters at the end and makes sortedIndexes length smaller
    if (s.indexOf(uniqueLetters[x]) !== -1) {
      indexes.push(s.indexOf(uniqueLetters[x]))
    }
  }
  let sortedIndexes = indexes.sort( (a,b) => a - b)
  let last = sortedIndexes.length
  let substring = s.slice(sortedIndexes[0], sortedIndexes[last-1]+1)
  // invalid word check
  if (sortedIndexes.length < uniqueLetters.length) {
    substring += "*"
  }

  return substring
}
console.log(shortestSubstring("dabbcabcd"));
console.log(shortestSubstring("dabbbbbbcabc"));
console.log(shortestSubstring("d"));
console.log(shortestSubstring("dds"));
console.log(shortestSubstring("dd"));
console.log(shortestSubstring("ddadaxxxx"));
console.log(shortestSubstring("xxcxxddadaxxxcx"));

Output

abcd
dabbbbbbc
d
dds
d
ddadax
daxxxc

Analysis

My strategy for solving this problem was to to first filter out all of the unique characters in the string and then loop through the string to cut out the substrings with all of unique characters in it. I used a while loop that terminates when the length of the copied input string length is equal to 0. Within the while loop, a findStr function checks for each unique letter in the input string and returns that string. I did a hacky thing where I added an “*” to the end of a substring if it was the end of the inputted string and was missing any of the unique letters. The length of the returned substring decrements the length of the copied input string length. I filter out any substring with “*” in it and find the shortest substring.

Make Anagram

An anagram is a word, phrase, or name formed by rearranging the letters of another, such as cinema, formed from iceman. This problem gives 2 input strings and finds the number of deletes that are needed to make the 2 input strings anagrams of each other.

function makeAnagram(a, b) {
  let counter = {};
  let total = 0;
  let arrA = a.split('')
  let arrB = b.split('')
arrA.forEach(char => {
    if (counter[char]) {
      counter[char] = counter[char]
    } else {
      counter[char] = 0
    }
    counter[char]++;
  })
arrB.forEach(char => {
    if (counter[char]) {
      counter[char] = counter[char]
    } else {
      counter[char] = 0
    }
    counter[char]--;
  })
  Object.keys(counter).forEach(k => {
    if (counter[k] !== 0) {
        total += Math.abs(counter[k]);
    }
  })
return total;
}
console.log(makeAnagram("cdex", "abcx"));
console.log(makeAnagram("cde", "abc"));
console.log(makeAnagram("fcrxzwscanmligyxyvym", "jxwtrhvujlmrpdoqbisbwhmgpmeoke"));

Output

4
4
30

Analysis

I split the 2 strings into arrays and iterate through each to get a count of occurrences of each letter. If the letters are found in both strings, string a increments in the count object and string b decrements it. In the end, it checks the count object to see if any of the keys have values that aren’t equal to 0 and adds their absolute value to the total number of deletes needed to make the two strings an anagram. An example of what the counter looks like for console.log(makeAnagram(“cdex”, “abcx”));:

{ c: 0, d: 1, e: 1, x: 0, a: -1, b: -1 }

Sherlock and the Valid String

Sherlock considers a string to be valid if all characters of the string appear the same number of times. It is also valid if he can remove just character at index in the string, and the remaining characters will occur the same number of times. Given a string , determine if it is valid. If so, return YES, otherwise return NO.

Sample Input 1

aabbcd

Sample Output 1

NO

Explanation 1

Given , we would need to remove two characters, both c and d aabb or a and b abcd, to make it valid. We are limited to removing only one character, so is invalid.

Sample Input 2

abcdefghhgfedecba

Sample Output 2

YES

Explanation 2

All characters occur twice except for which occurs times. We can delete one instance of to have a valid string.

function isValid(s) {
  let arr = s.split('')
  let counter = {}
  for (let i = 0; i < s.length; i++) {
    if (counter[s[i]]) {
      counter[s[i]]++
    } else {
      counter[s[i]] = 1
    }
  }
let prev = counter[Object.keys(counter)[0]]
  let removed = 0
  for (let i = 1; i < Object.keys(counter).length; i++) {
    if (prev === counter[Object.keys(counter)[i]]) {
      prev = counter[Object.keys(counter)[i]]
    } else if (prev !== counter[Object.keys(counter)[i]] &&
        counter[Object.keys(counter)[i]]-1  === prev) {
          //check for if the count is equal to the normal count - 1
    }
    else if (prev !== counter[Object.keys(counter)[i]] &&
        counter[Object.keys(counter)[i]]-1  === 0) {
          removed++
    } else {
      return "NO"
    }
  }
if (removed > 1) {
    return "NO"
  }
return "YES"
}
console.log(isValid("abc"));
console.log(isValid("abcc"));
console.log(isValid("aabbcd"));
console.log(isValid('aabbccddeefghi'));
console.log(isValid('abcdefghhgfedecba'));
console.log(isValid('abcdefghhgfedecbaa'));
console.log(isValid('aabbc'));

Output

YES
YES
NO
NO
YES
NO
YES

Analysis

Similar to the last problem, I make a counter object to count the number of occurrences of each letter. Each letter has to have the same count, except for one that be valid if its count can be decremented to equal the same count as the others. I do this by keeping track of the previous count of each iteration and doing checks for if the count of each element is equal to the others or if it is +1. There is also a check to see if the +1 is being removed more than once because if it happens more than once, it is invalid. If any of these checks don’t pass, it returns NO, otherwise it returns YES.

Thanks for reading!