Topics
String

Longest Common Prefix (opens in a new tab)

  • The main function iteratively updates the common prefix by comparing it with each string in the array.
  • The getCommonPrefix function constructs the common prefix by comparing characters one by one until a mismatch occurs.
/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function(strs) {
    let i =0;
    if(strs.length===1)
        return strs[0];
    let result ="";
     result += getCommonPrefix(strs[0], strs[1]);
    for(let i=2;i<strs.length;i++){
       result= getCommonPrefix(result, strs[i]);
    }
    return result;
};
 
function getCommonPrefix(str1, str2){
    let longStr;
    let smallStr;
    let result="";
    if(str1[0] !== str2[0])
        return "";
   if(str1.length<=str2.length){
       longStr = str2;
       smallStr = str1;
   }
    else{
        longStr = str1;
       smallStr = str2;
    }
   for(let i=0;i<smallStr.length;i++){
       if(longStr[i]=== smallStr[i]){
           result+=longStr[i];
       }
       else{
           return result;
       }
    } 
    return result;
}
Complexity
  • Time: O(N * M)
    • Where N is the number of strings and M is the length of the shortest string among all the strings.
  • Space: O(M)
    • Where M is the length of the shortest string among all the strings.

Reverse Words in a String (opens in a new tab)

  • Convert the string into an array of words and push the array of words (except empty space)
  • Reverse the resultant array and covert the array into string with space between words
/**
 * @param {string} s
 * @return {string}
 */
var reverseWords = function (s) {
  let words = s.split(' ');
  let result = [];
  for (const word of words) {
    if (word.length) {
      result.push(word);
    }
  }
  return result.reverse().join(' ');
};
Complexity
  • Time: O(n)
  • Space: O(n)

Valid Anagram (opens in a new tab)

  • Create an object called "count" , with key as character of string and value as count of that character in the string
  • Loop through those two strings , one with increasing of count and other with decreasing of count
/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
 
var isAnagram = function(s, t) {
    if(s.length !== t.length)
        return false;
    
    let count={};
 
    for(let char of s){
        count[char] = (count[char] || 0) + 1;
    }
    
    for(let char of t){
        if(!count[char])
            return false;
         count[char]--;
    }
    return true;
};
Complexity
  • Time: O(n)
  • Space:
    • O(1) : If the character set is fixed (e.g., ASCII), the space required for the count object is O(1) since the number of unique characters is constant (256 for extended ASCII).
    • O(k) : For Unicode or larger character sets, the space required could be O(k), where k is the number of unique characters in the input.

Find All Anagrams in a String (opens in a new tab)

  • Use Sliding window technique and check the every window is Anagram or not
  • if any window is Anagram, add its index to "res" array
/**
 * @param {string} s
 * @param {string} p
 * @return {number[]}
 */
var findAnagrams = function(s, p) {
    let res = [];
    let pCount = {};
    let sCount = {};
    let pLen = p.length;
    let sLen = s.length;
 
    // Populate the frequency count for the pattern p
    for (let char of p) {
        pCount[char] = (pCount[char] || 0) + 1;
    }
 
    // Initialize the frequency count for the first window of size p in s
    for (let i = 0; i < pLen; i++) {
        sCount[s[i]] = (sCount[s[i]] || 0) + 1;
    }
 
    // Compare the frequency count of the first window
    if (isSameCount(pCount, sCount)) {
        res.push(0);
    }
 
    // Slide the window over string s
    for (let i = pLen; i < sLen; i++) {
        // Add the new character to the current window count
        sCount[s[i]] = (sCount[s[i]] || 0) + 1;
        // Remove the character that is no longer in the window
        let startChar = s[i - pLen];
        if (sCount[startChar] > 1) {
            sCount[startChar]--;
        } else {
            delete sCount[startChar];
        }
        // Compare the frequency count of the current window
        if (isSameCount(pCount, sCount)) {
            res.push(i - pLen + 1);
        }
    }
 
    return res;
};
 
// Helper function to compare two frequency count objects
const isSameCount = function(count1, count2) {
    if (Object.keys(count1).length !== Object.keys(count2).length) {
        return false;
    }
    for (let key in count1) {
        if (count1[key] !== count2[key]) {
            return false;
        }
    }
    return true;
};
Complexity
  • Time: O(n)
    • The sliding window ensures that each character in s is processed only once.
    • The comparison of frequency counts is efficient and does not depend on the length of s.
  • Space: O(1)
    • The space used by the frequency count objects is limited to the number of distinct characters in p and s, which is constant (26 letters for lowercase English letters).

Rotate String (opens in a new tab)

  • check the input "goal" is contained in the concatination of the input "s" with itself and the both input length should same
/**
 * @param {string} s
 * @param {string} goal
 * @return {boolean}
 */
var rotateString = function (s, goal) {
  return s === goal || (s + s).includes(goal) && s.length === goal.length;
};
Complexity
  • Time: O(n)
  • Space: O(n)

Check If Two String Arrays are Equivalent (opens in a new tab)

  • Having 2 array, convert array into string, with one by one check if every character matches return true else false
/**
 * @param {string[],string[]} nums
 * @return {boolean}
 */
const stringComparison = (word1, word2) => {
  let word1String = word1.join('');
  let word2String = word2.join('');
  if (word1String?.length != word2String?.length) return false;
 
  for (let i = 0; i < word1String?.length; i++) {
    if (word1String[i] != word2String[i]) {
      return false;
    }
  }
  return true;
};
Complexity
  • Time: O(n)
  • Space: O(1)

Largest Odd Number in String (opens in a new tab)

  • Find the lastOddNum in string and slice the string from 0 to lastOddNum index
/**
 * @param {string} num
 * @return {string}
 */
var largestOddNumber = function(num) {
    if(num & 1)
        return num;
    let lastOddNum = getLastOddNum(num);
    if(num.length>1){
        let i = num.lastIndexOf(lastOddNum)
        return num.slice(0,i+1);
    }
    return "";
};
 
function getLastOddNum(num){
    for(let i=num.length-1;i>=0;i--){
      if(num[i] & 1 === 1)
          return num[i];
    }
}
Complexity
  • Time: O(n)
  • Space: O(n)

Valid Palindrome (opens in a new tab)

  • The program cleans the input string by keeping only alphanumeric characters and converting them to lowercase.
  • It then checks if the cleaned string is equal to its reverse to determine if it is a palindrome.
/**
 * @param {string} s
 * @return {boolean}
 */
var isPalindrome = function (s) {
  let cleanedStr = '';
 
  // Helper function to check if a character is alphanumeric
  function isAlphanumeric(char) {
    return /^[a-zA-Z0-9]+$/.test(char);
  }
 
  // Build the cleaned string with only alphanumeric characters
  for (let char of s) {
    if (isAlphanumeric(char)) {
      cleanedStr += char.toLowerCase();
    }
  }
 
  // Compare the cleaned string with its reverse
  let reversedStr = cleanedStr.split('').reverse().join('');
  return cleanedStr === reversedStr;
};
Complexity
  • Time: O(n)
  • Space: O(n)

Longest Palindrome (opens in a new tab)

  • The program counts the frequency of each character in the input string s and calculates the length of the longest palindrome that can be formed using those characters.
  • It adds 2 to the length for every pair of characters and includes a central character if the original string length is greater than the count of pairs.
/**
 * @param {string} s
 * @return {number}
 */
var longestPalindrome = function(s) {
  let longestCount = 0;
  let charCountObj = {};
 
    for (const char of s) {
        charCountObj[char] = (charCountObj[char] || 0) + 1;
        if (charCountObj[char] % 2 == 0) longestCount += 2;
    }
    return s.length > longestCount ? longestCount + 1 : longestCount;
};
Complexity
  • Time: O(n)
  • Space: O(n)
ArrayMath