Do it for FUN | SUMFIのBlog

[LeetCode] Count Substrings That Differ by One Character 2022-07-07|PSLeetCode|Problem Solving-Dynamic Programming

1638. Count Substrings That Differ by One Character

Given two strings s and t, find the number of ways you can choose a non-empty substring of s and replace a single character by a different character such that the resulting substring is a substring of t. In other words, find the number of substrings in s that differ from some substring in t by exactly one character.

For example, the underlined substrings in “computer” and “computation” only differ by the ‘e’/‘a’, so this is a valid way.

Return the number of substrings that satisfy the condition above.

A substring is a contiguous sequence of characters within a string.

[LeetCode] The k-th Lexicographical String of All Happy Strings of Length n 2022-07-07|PSLeetCode|Problem Solving-Back Tracking

1415. The k-th Lexicographical String of All Happy Strings of Length n

A happy string is a string that:

consists only of letters of the set [‘a’, ‘b’, ‘c’].

s[i] != s[i + 1] for all values of i from 1 to s.length - 1 (string is 1-indexed).

For example, strings “abc”, “ac”, “b” and “abcbabcbcb” are all happy strings and strings “aa”, “baa” and “ababbc” are not happy strings.

Given two integers n and k, consider a list of all happy strings of length n sorted in lexicographical order.

Return the kth string of this list or return an empty string if there are less than k happy strings of length n.

[LeetCode] Find the Longest Substring Containing Vowels in Even Counts 2022-07-07|PSLeetCode|Problem Solving-Hash Table-Bit Manipulation

1371. Find the Longest Substring Containing Vowels in Even Counts

Given the string s, return the size of the longest substring containing each vowel an even number of times. That is, ‘a’, ‘e’, ‘i’, ‘o’, and ‘u’ must appear an even number of times.

[LeetCode] Reduction Operations to Make the Array Elements Equal 2022-07-07|PSLeetCode|Sorting-Problem Solving-Math

1887. Reduction Operations to Make the Array Elements Equal

Given an integer array nums, your goal is to make all elements in nums equal. To complete one operation, follow these steps:

Find the largest value in nums. Let its index be i (0-indexed) and its value be largest. If there are multiple elements with the largest value, pick the smallest i.

Find the next largest value in nums strictly smaller than largest. Let its value be nextLargest.

Reduce nums[i] to nextLargest.

Return the number of operations to make all elements in nums equal.