umma.dev

Algorithms + Data Structures: Strings

As part of the Algorithms and Data Structures series, this part covers strings. Here I give examples of functions used for strings and how to use them when solving problems.

String Functions

concat
const stringOne = "Hello";
const stringTwo = "World";

console.log(stringOne + stringTwo); //HelloWorld
index
const example = "Here is the example";
const search = "example";

const indexOfItem = example.indexOf(search);

console.log(indexOfItem); // 12
const example = "Here is the example";
let index = 5;

const findWord = example.at(index);

console.log(findWord); // i
const example = "Here is the example";
const index = 5;

const findChar = example.chartAt(index);

console.log(findChar); // i
const example = "Here is the example Here";
const search = "Here";
console.log(`The last index is ${example.lastIndexOf(search)}`); // "The last index is 20"
split
const string = "Here is a sentence.";

const words = string.split(" ");
const chars = string.split("");
const copyStr = string.split();

console.log(words[1]); // is
console.log(chars[1]); // e
console.log(copyStr); // ["Here is a sentence."]
substring
const string = "Hello";
const subStr = string.substring(1, 3);
const subStrTwo = string.substring(2);

console.log(subStr); // el
console.log(subStrTwo); // llo
lower/upper case
const str = "TeSt";
const lowerCase = str.toLowerCase();
console.log(lowerCase); // test
const dotted = "İstanbul";
const lowerCaseLocale = dotted.toLocaleLowerCase("tr");
console.log(lowerCaseLocale); // istanbul
const str = "TeSt";
const upperCase = str.toUpperCae();
console.log(upperCase); // TEST
const city = "istanbul";
const upperCaseLocale = city.toLocaleUpperCase("TR");
console.log(upperCaseLocale); // İSTANBUL
trim
const str = "   Hello world!   ";
console.log(str.trim()); // "Hello world!"
const str = "   Hello world!   ";
console.log(str.trimStart()); // "Hello world!    "
const str = "   Hello world!   ";
console.log(str.trimEnd()); // "    Hello world!"
repeat
const repeatStr = " again";
console.log(`Repeat${repeatStr.repeat(4)}`); //Repeat again again again again
replace
const replaceStr = "Replace something please.";
console.log(replaceStr.replace("something", "test")); // "Replace test please."
const replaceAllStr = "Replace something with something please.";
console.log(replaceAllStr.replaceAll("something", "test two")); // "Replace test two with test two please"
search (regex)
const str = "Here is the string.";
const regex = /[^\w\s]/g;

console.log(str.search(regex)); //18
slice
const str = "Here is the string.";
console.log(str.slice(10)); // "e string"
console.log(str.slice(1, 2)); // "e"
console.log(str.slice(-1, -2)); // ""
stars/ends with
const str = "This is the start.";
console.log(str.startsWith("This")); // true
console.log(str.startsWith("star")); // false
console.log(str.startsWith("star", 4)); // false
const str = "This is the end.";
console.log(str.endsWith(".")); // true
console.log(str.endsWith(".", 10)); // false
match
const str = "There is a match somewhere.";
const regex = /[A-Z]/g;
console.log(str.match(regex)); //["T"]
const regexp = /t(e)(st(\d?))/g;
const str = "test1test2";

const array = [...str.matchAll(regexp)];

console.log(array[0]); // ["test1", "e", "st1", "1"]
console.log(array[1]); // ["test2", "e", st2", "2"]
includes
const str = "This sentence includes lots of words.";
const word = "includes";
console.log(str.includes(word)); // true
reverse
const reverseMe = "test";
const print = reverMe.split("").reverse().join("");
console.log(print); //["t", "s", "e", "t"]
function reverseStr(str) {
  const newStr = ""
  for(let i=str.length - 1; i>=0; i==) {
    newStr += str[i]
  }
  return newStr
}
reverseStr("hello")
function reverseStrRecursion(str) {
  return (str === '') ? '' : reverseStrRecursion(str.substring(1)) + str.charAt(0)
}
reverseStrRecursion("hello")

Problem Sets

Easy

Caesar Cipher Encryptor

Given a non-empty string of lowercase letters and a non-negative integre representing a key, write a function that returns a new string obtained by shifting every letter in the input string by k positions in the alphabet, where k is the ky.

The letters should “wrap” around the alphabet, the letter z shifted by one returns the letter a.

Sample Input

string = "xyz"
key = 2

Sample Output

"zab"

Code Given

function caesarCipherEncryptor(string, key) {
  // Write your code here.
}

Answer

function caesarCipherEncryptor(string, key) {
  let str = "";

  for (let i = 0; i < string.length; i++) {
    let k = string.charCodeAt(i) + (key % 26);
    str += String.fromCharCode(k < 123 ? k : (k % 122) + 96);
  }
  return str;
}
Medium

Valid IP Addresses

You are given a string of length 12 or smaller, containing only digits. Write a function that returns all the possible IP addresses that can be created by inserting three .s in the string. An IP address is a sequence of four positive integers that are separated by .s, where each individual integer is within the range of 0 - 255.

Sample Input

string = "1921680

Sample Output

[
  "1.9.216.80",
  "1.92.16.80",
  "1.92.168.0",
  "19.2.16.80",
  "19.2.168.0",
  "19.21.68.0",
  "19.21.6.80",
  "19.216.8.0",
  "192.1.6.80",
  "192.1.68.0",
  "192.16.8.0"
]

Code Given

function validIPAddress(string) {
  return [];
}

Answer

function validIPAddresses(digits, octets = [], validIPs = []) {
  const numDigits = digits.length
  const numGroup = octets.length
  const maxRemain = 12 - numGroup * 3
  const minRemain = 4 - numGroup

  if(numDigits > maxRemain || numDigits < minRemain) {
    return []
  } else if(numDigits === 0) {
    validIPs.psuh(octets.join('.'))
  }

  for(let i = 1; i<=Math.min(4, numDigits); i++) {
    const octet = digits.slice(0, i)
    const truncDigits = digits.slice(i)

    if(Number(octet) > 255) continue
    if(octet.length > 1 && octet[0] === '0) continue

    const addNewOctet = [...octets, octet]
    validIPAddresses(truncDigits, addNewOctet, validIPs)
  }
  return validIPs
}
Hard

Longest Substring Without Duplicates

Write a function that takes in a string and returns its longest substring without duplicate characters.

Sample Input

string = "clementisacap

Sample Output

"mentisac"

Code Given

function longestSubstringWithoutDuplication(string) {}

Answer

function longestSubstringWithoutDuplication(string) {
  let windowStart = 0,
    longest = [0, 1],
    charIndexMap = {};

  for (let windowEnd = 0; windowEnd < string.length; windowEnd++) {
    const rightChar = string[windowEnd];
    if (rightChar in charIndexMap) {
      windowStart = Math.max(windowStart, charIndexMap[rightChar] + 1);
    }
    if (longest[1] - longest[0] < windowEnd + 1 - windowStart) {
      longest = [windowStart, windowEnd + 1];
    }
    charIndexMap[rightChar] = windowEnd;
  }
  return string.slice(longest[0], longest[1]);
}