Skip to content
DevGod Repo
Blog

String

8 posts with the tag “String”

Leetcode 58: Length Of Last Word

DevGod
DevGod
Elf Vtuber

Question

In this Leetcode question, we are given a string representing a sentence. Each word is separated by the ” ” space character. Our goal is to return the length of the last word in the string. An important observation to note is that our given string could have white space characters before the start, as well as after the end. Additionally, more than one white space character could also separate each word in the string.

Solving

To solve this Leetcode problem, I start by using the built-in JS .trim() method. This trim method is able to remove all white space at the beginning and end of the string. By using trim on the given string, I can proceed with my JS methods knowing the end of the string is just the last word, and no additional space characters.

Next I use the string .split(” ”) method to split in-between space characters. This method transforms our trimmed string into an array of strings, separated by the space characters. As a side note, this method does leave some empty elements, but that is alright since the last element will just be our full last word. Since we are only concerned about the last element of this split array, any empty strings present in this string array can just be ignored. There is a way to use regular expressions to more accurately split the given string to avoid empty strings. However since I was more interested in code brevity, I instead used just a ” ” single space character instead.

After splitting our trimmed string into an array of strings, we can now pop() to return the last element. The pop method is a built-in JS array method, that removes and returns the last word of the split string array. Another way to retrieve the last element would have been with [s.trim().split(” “).length - 1]. While this is the slightly more time efficient way, the .pop() method just took less characters. Given the small constraints regarding the given string’s length, I preferred the least amount of code vs the most time efficient code.

Lastly, now that we have trimmed the original string, split it into an array of strings and popped the last element, we can now just return the .length property to answer the question.

TLDR:

I used built-in Javascript array and string methods to return the length of the last word in the given string.

Leetcode 763: Partition Labels

DevGod
DevGod
Elf Vtuber

For today’s daily leetcode problem, we are given a string and need to split it into as many partitions as possible, ensuring that each letter appears in at most one partition. Additionally, the partitions must preserve the order of letters as they appear in the original string. However, we don’t need to store the actual substrings—our task is simply to return the lengths of these partitions.

Example Walkthrough Consider the string “pizzatime”. The optimal partitions would be [1,6,1,1]. Here’s why:

  • The letters p, m, and e each form their own single-letter partitions since they don’t share any letter with another partition.

  • The substring “izzati” forms a partition because it contains multiple occurrences of i and z, and we need to ensure that all instances of a letter belong to a single partition.

  • Since the letters must remain in order and cannot belong to multiple partitions, “zzati” is grouped together with i to form a partition of length 6.

Another example is “partitionlabels”, which results in [1,13,1]:

  • The letters p and s form their own separate partitions.

  • The middle partition, “artitionlabel”, must include all occurrences of a and l.

  • Since l appears late in the string, we must extend the partition to ensure all ls are included, resulting in a large middle partition.

Implementation Approach Since I was in a hurry and the constraints were small, I used JavaScript’s built-in .lastIndexOf() method to determine the last occurrence of each letter in real time. The key insight is that a letter’s last occurrence dictates where a partition must end. While this approach runs in 𝑂(n^2) time due to repeated .lastIndexOf() calls, an optimized solution could use a hashmap for 𝑂(1) lookups.

To efficiently track when to end a partition, I maintain a max variable, representing the farthest last occurrence seen so far. As I iterate through the string, I update max using:

max = Math.max(max, s.lastIndexOf(s[L]));

This ensures that if a previous letter has a later last occurrence, we extend the current partition accordingly. This is crucial for cases like “partitionlabels”, where encountering l extends the partition beyond a’s last occurrence.

I iterate through the string using a loop and keep track of partitionSize. Whenever I reach max, I add partitionSize to the result array, reset it, and continue. Instead of constructing substrings, I only track partition lengths, as that’s all the problem requires.

This greedy approach ensures an optimal partitioning of the string while keeping the implementation simple and efficient.

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

DevGod
DevGod
Elf Vtuber

Another backtracking problem where you are given some letter options to choice from to arrange permutations to explore. This one is a bit different cause you are tasked with finding all permutations containing just ‘a’, ‘b’ or ‘c’ letters, with no duplicates. For example a happy permutation is “abc”, and a non happy one would be ‘aab’.

You are given N for the amount of letters that should be in your generated sequence, and K for finding the Kth seqence if you were to sort all the seqences you found in a list. I like how leetcode’s hints tonight casually tried to get you to use more memory then you would need to.

Instead of generating an array of all my possible seqences, I just greedily backtrack using the already lexigraphically sorted string “abc”. I then just use a score varible to keep track of which Kth seqence I am currently at. If I have reached the Kth seqence, I just return out of my backtrack function and then return the answer.

Lastly, I know for sure there has to be some really cool math combinatrics trick for this problem, but I just couldn’t think of it, EI the backtracking for it just being seqences of 10 letters or less worked pretty well, but im sure if it were harder constraints I would be forced to somehow optimally use math to spit out a seqence.

Leetcode 2516: Take K of Each Character From Left and Right

DevGod
DevGod
Elf Vtuber

About

This leetcode problem asks use to find the minimal number of operations needed to get AT LEAST k amounts of a, b and c characters. For each operation, you are able to either remove a letter from the beginning or end of the given string.

Example

“aabaaaacaabc” k=2

The minimal number of operations needed would be 8. From the left of the given string we can remove letters “aab”. From the right of the given string we can remove letters “caabc”. With these 8 removal operations, we can get 4 a’s, 2 b’s and 2 c’s, which meet our “AT LEAST” k of each letter requirement.

Thoughts

At first, I was thinking it was some kind of greedy deque problem. At first glances, It felt like the problem was asking to choose optimally between either the left side vs the right side of the char array.

However, I then realized that it sounded more like finding an optimal prefix and suffix of the string such that you had all the letter you needed. Seeing I was finding a string prefix and suffix, I knew that I would need some kind of Two Pointer approach for this problem.

After getting a little frustrated, I peaked at the topic tags and saw “Sliding Window”. Then it clicked, a lot of Leetcode sliding window problems are phrased like, for this continuous sub array in your array of data, find X criteria or frequencies. This problem sounded similar, but the main difference was we are concerned about what is on the outside of the sliding window, versus what’s on the inside of the sliding window.

Implementation

In Javascript, I first find the frequencies of a,b and c present in my given string. If the amount of letters in the whole string are less than K for any of the letters, I then just return a -1. If the amount of letters in the whole string are greater than K, a while loop is used to start building my sliding window.

During each iteration, sliding window’s R pointer slides to the right, and for each letter it comes across it subtracts from my frequency map of letters. If at any point a letter’s frequency becomes less than K, I start moving the left pointer to the right. For each letter my left pointer hits, I increase the frequency of that letter in the frequency map.

This ensures that my sliding window never takes more letters than it can from the string prefix or suffix. In other words, this makes sure that my sliding window is the largest window of characters that can take up the space between the smallest need prefix and suffix of the string.

Lastly, for each iteration we keep track of the maxRange of our sliding window. We then return the given string length - maximum range of the sliding window. We return this because the minimal of letter removal operations is equal the amount of character not present inside our sliding window. The answer therefor is basically the smallest possible string prefix and string suffix.

TLDR

  1. Find the minimal number of letters from beginning or end of string to remove for “at least” K letters.

  2. At first thought it was a greedy problem, but it’s actually a slightly unusual sliding window / two pointers problem.

  3. Use Sliding window to find the largest range between the smallest needed prefix and suffix of string.

  4. The sliding window is valid if your remaining letter frequencies do not go below K elements.

Closing Thoughts

This is a very interesting sliding window problem. Instead of following the usual pattern of focusing on the internal state of the Sliding window element frequencies, it focuses on how your sliding window impacts the external state of you total frequencies of each letter in the given string.

Leetcode 1106: Parsing A Boolean Expression

DevGod
DevGod
Elf Vtuber

About

The goal of this problem is to take a string representation of booleans and functions, then return the expected boolean value after completing the function. For example, we could have a “t” symbol for a true boolean, a “f” symbol for a false boolean, a ! for a not function, and a & and | for functions that take all elements inside of a () and return the boolean of bitwise anding and bitwise or ing all elements respectively.

For example:

  1. &(|(f)) = Return the bitwise or of one false, then return the bitwise & of one false
  2. |(f,f,f,t) = Return the bitwise or of three falses and one true
  3. !(&(f,t)) = Find the bitwise and of both false and true, then return the flipped / inverted result.

Thoughts

After reading the problem, I stopped panicking about its high difficulty rating and thought back to reading up on JSFuck and BrainFuck, so decided to just make an eval statement do the work for me. I knew this would be like implementing a very minimal programming language interpreter, since “t” and “f” are like boolean constants, and the !&| symbols are like functions that accept input and return an output value.

Implementation

First I use a series of replaceAll commands to slightly edit the given expression. A big reason for replacing these symbols is due to the fact that JS functions can not be just one special character like !&|, since those characters are reserved for bitwise operations. Once I have my expression edited, I then append some string representations of JS functions for returning the flipped value of a given boolean, as well as returning the bitwise OR / AND of all elements given in the function’s args. Lastly, I then return the result given by running the JS eval command with my slightly modified string.

Leetcode 921: Minimum Add To Make Parentheses Valid

DevGod
DevGod
Elf Vtuber

About

This problem is very similar to yesterday’s problem. The main difference is instead of swapping characters that are already present in the string, we are appending either a ”(” or a ”)” anywhere we want in the string. However, we still have the same goal of finding the minimal number of operations needed to achieve a balanced string of () such that each opening symbol ( has a corresponding symbol ).

For example

  1. ((), needs 1 ) symbol at the end to become balanced
  2. ()()() is already balanced, so return 0
  3. ))) needs 3 opening symbols to become balanced

Thoughts

My thoughts immediately jumped to yesterday. The only difference is I ended up having two variables, one for the remainder of unmatched opening symbols, and one for the unmatched closing symbols. Once I was able to find these two values, at first I mistakenly thought it was some sort of find the max value between them. But in practice, it is the addition of both values together to get the minimal number of additions needed to balance the string.

Implementation

Here in JS, I use a for loop to iterate through the test case string, while also finding the leftmost character & the rightmost character. After I have these varibles, I am then able to move left to right to calculate the remainder of opening ( symbols, while also moving right to left to find the remainder of closing ) symbols. After my for loop is completed, I then return the amount of unmatched opening ( symbols plus the amount of matched closing symbols ) together.

Leetcode 1963: Minimum Number of Swaps to Make the String Balanced

DevGod
DevGod
Elf Vtuber

About

This leetcode problem is basically us to find the minimum number of swap operations are needed to make a string of ”[]” symbols balanced. Balanced being if each opening ”["" symbol also has a closing ”]” symbol. For example, the following would be examples of balanced strings.

  1. []
  2. [[]]
  3. [][][]

Thoughts

One thing to notice off the bat is when considering certain testcases, it is already possible that a string already contains a balanced string. For example, testcase ]][][[ already has a balanced string in the middle, so it is the same as ]][[. For example, all testcases either eventually become testcases such as ][, ]][[, ]]][[[ ect.

After we see this, it is now about finding a remainder inside our testcase string of extra unmatched chars. For example, in ][ the remained would be one, which can be viewed either as having one unmatched opening char, or one unmatched closed char.

After drawing out these certain testcases, I saw a certain pattern involving the remaining total of unmatched charecters in the sring.

  1. ][ = 1 Swaps needed
  2. ]][[ = 1 Swaps needed
  3. ]]][[[ = 2 Swaps needed
  4. ]]]][[[[ = 2 Swaps needed
  5. ]]]]][[[[[ = 3 Swaps needed

The pattern being, that for the remaining amount of unmatched symbols at the end of the string is then Math Ceil (remaining amount of unmatched chars / 2) is the number of swaps needed.

Implementation

There are two ways you can solve this problem. One way is to use a stack data structure to keep track of previous symbols, and then pushing and popping accordingly. However, what I ended up doing to save memory usage was to simulate the stack size instead. Since we only need to return the minimal amount of swaps needed, we don’t need to have a stack, only the state of the would be stack’s size / length. Once I for loop to simulate the stack size, I simply just return the Math.ceil(remainder / 2) to return the minimal amount of swaps needed.

Leetcode 2696: Minimum String Length After Removing Substrings

DevGod
DevGod
Elf Vtuber

About

This problem is basically asking after you replace every occurrence of a substring “AB” or “CD” in your testcase string, return the length of the new string. For example:

  1. “ABCDZ” => “Z” => return 1;
  2. “QABABABQ” => “QQ” => return 2;
  3. “ACDB” => "" return 0;

Thoughts

The first two example testcases are pretty straight forward. Just remove “AB” substrings, then remove all “CD” substrings. However, the third testcase gets interesting where we remove “AB”, then remove “CD”. However, after removing the “CD” we are left with “AB”, which can then be removed again to return a blank string "" / a return string length of 0. After seeing this I immediately just wanted to use regular expressions, as that would be perfect for finding substrings present in my main string, as well as for preforming replaceAll operations to remove “AB” and “CD” substrings from the main testcase string.

Implementation

I simply just made a while loop that only ends once my given String s no longer has a “AB” or a “CD” substring present inside of itself. This is done by using the regular expression /AB|CD/, which just checks for any occurrence of an “AB” or “CD”. The .test(s) then just takes my regular expressions, searches the string using said regular expression, then returns true or false.

Inside my while loop, I then use s.repalceAll and /AB|CD/g to replace all occurrences of ABs and CDs from my current string. The regular expression is pretty similar to the top, I just use G to make sure its global since it’s a replace all.

Lastly, once my String S no longer has any occurrences of substrings “AB” or “CD”, I exit my while loop and then just return the length of my now AB and CD substring freed string.