DEV Community: Shiki Endou

Solving the 'Container With Most Water' on LeetCode with C++

Shiki Endou — Thu, 10 Aug 2023 02:32:27 +0000

Problem

https://leetcode.com/problems/container-with-most-water/description/

Answer

class Solution {
public:
    int maxArea(vector<int>& height) {
        int maxArea = 0;
        int left = 0;
        int right = height.size() - 1;

        while (left < right) {
            int h = min(height[left], height[right]);
            int w = right - left;
            maxArea = max(maxArea, h * w);

            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }

        return maxArea;
    }
};

Let's consider a solution to this problem.

We want to find a container that can hold the most water. This is calculated as the maximum value derived from multiplying the height and width (between two bars).

How do we find the height and width?

The maximum width (distance between two bars) is between the first and last bars.

For example, in the array [3, 2, 4, 2, 5], the first bar (index 0) and the last bar (index 4) offer the maximum width.

So we begin finding a container with the most water from both ends.

We then move to the next index. However, we are unsure which index to move to.

We move the index with the smaller height to the next one. This is because we aim to find a container with the most water, hence we should continue selecting a taller height.

For example, in the array [3, 2, 4, 2, 5], the first bar (index 0) and last bar (index 4) provide the maximum width. The container size is 12 (height 3 * width 4), and the height used is determined by the shorter bar.

Then, the indices are 1 (height 2) and 4 (height 5) because we should continue to select a taller height. The container size is 6 (height 2 * width 3).

The next indices are 2 (height 4) and 4 (height 5). The container size is 8 (height 4 * width 2).

The final indices are 3 (height 2) and 4 (height 5). The container size is 2 (height 2 * width 1).

The container that holds the most water has a size of 12 (when indices are 0 and 4).

We converts the above algorithm to code.
I repost the answer code.

class Solution {
public:
    int maxArea(vector<int>& height) {
        int maxArea = 0;
        int left = 0;
        int right = height.size() - 1;

        while (left < right) {
            int h = min(height[left], height[right]);
            int w = right - left;
            maxArea = max(maxArea, h * w);

            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }

        return maxArea;
    }
};

        int maxArea = 0;
        int left = 0;
        int right = height.size() - 1;

The code starts from the first and last indices because the width is at its maximum.

        while (left < right) {

        }

We continue comparing containers until the left index is less than or equal to the right index.

        while (left < right) {
            int h = min(height[left], height[right]);
            int w = right - left;
            maxArea = max(maxArea, h * w);

The 'h' variable takes the smaller height from the left or right index, because the container height is determined by the shorter bar.

The 'w' variable is obtained by subtracting the left index from the right one.

The 'maxArea' variable stores the larger area between the old and the new one.

            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }

After calculating the area from the height and width, we move the index that has the smaller height because a larger height could yield a larger area.

That's all.

Solving the 'Palindrome Number' on LeetCode with C++

Shiki Endou — Wed, 02 Aug 2023 09:08:18 +0000

Problem

https://leetcode.com/problems/palindrome-number/

Answer

class Solution {
public:
    bool isPalindrome(int x) {
        if (x < 0) return false;

        long reversedX = 0;
        int originalX = x;
        while (x != 0) {
            reversedX = reversedX * 10 + x % 10;
            x /= 10;
        }

        return originalX == reversedX;
    }
};

Let's consider a solution to this problem.

We want to know whether an integer is a palindrome or not.

It's simple. If an integer and its reversed form are the same, we know the integer is a palindrome.

Let's analyze the solution as code.

        if (x < 0) return false;

Firstly, if the integer is negative, it's not a palindrome.

        long reversedX = 0;
        int originalX = x;

We define a long variable, reversedX, because it might exceed -2^31 or 2^31.

We define an int variable, originalX, because the value of x will change during the subsequent processes.

        while (x != 0) {
            reversedX = reversedX * 10 + x % 10;
            x /= 10;
        }

We want to reverse x. x % 10 gets the last digit of the integer.
For example, if x is 123, 123 % 10 gives us 3.
Then, we don't need the 3 of 123 and remove it using x /= 10.

This process continues until x is 0.

In the second loop, reversedX already has a value, so we need to add reversedX * 10 to x % 10.
For example, if x is 12 and reversedX is 3, 3 * 10 + 12 % 10 equals 30 + 2 = 32.

If we continue this process until x is 0, we will have reversed the integer.

Lastly, we can determine whether the original integer is a palindrome by comparing reversedX and originalX.

Solving the 'String to Integer (atoi)' on LeetCode with C++

Shiki Endou — Tue, 25 Jul 2023 10:50:17 +0000

Problem

https://leetcode.com/problems/string-to-integer-atoi/

Answer

#include <string>
#include <climits>

class Solution {
public:
    int myAtoi(string s) {
        int i = 0, sign = 1, result = 0;

        // Skip whitespaces
        while (i < s.size() && s[i] == ' ') {
            i++;
        }

        // Check the sign
        if (i < s.size() && (s[i] == '-' || s[i] == '+')) {
            sign = (s[i++] == '-') ? -1 : 1;
        }

        // Read in the digits and check for overflow/underflow condition
        while (i < s.size() && isdigit(s[i])) {
            if (result > INT_MAX / 10 || (result == INT_MAX / 10 && s[i] - '0' > INT_MAX % 10)) {
                return (sign == 1) ? INT_MAX : INT_MIN;
            }
            result = result * 10 + (s[i++] - '0');
        }

        return result * sign;
    }
};

Let's analyze the solution to the problem.

Assume the input is " -45string".

1.Read in and ignore any leading whitespace.

We need to convert " -45string" to "-45string", resulting in "-45string".

2.Check if the next character (if not already at the end of the string) is '-' or '+'. Read this character in if it is either. This determines if the final result is negative or positive respectively. Assume the result is positive if neither is present.

We need to check whether a sign is positive or negative.
The '-' sign is temporarily stored and the input becomes "45string".

Read in next the characters until the next non-digit character or the end of the input is reached. The rest of the string is ignored.

We check each character in order, until a non-digit character is encountered.

The input becomes "45".

Finally, we convert the string to an integer and add the sign (positive or negative).

The final output is -45.

Additionally, we must ensure that the integer does not exceed the limits of INT_MAX and INT_MIN.

If the integer is out of the 32-bit signed integer range [-231, 231 - 1], then clamp the integer so that it remains in the range. Specifically, integers less than -231 should be clamped to -231, and integers greater than 231 - 1 should be clamped to 231 - 1.

To adhere to the above constraints, we add conditions to the code.

Let's break down the code.

#include <string>
#include <climits>

class Solution {
public:
    int myAtoi(string s) {
        int i = 0, sign = 1, result = 0;

        // Skip whitespaces
        while (i < s.size() && s[i] == ' ') {
            i++;
        }

        // Check the sign
        if (i < s.size() && (s[i] == '-' || s[i] == '+')) {
            sign = (s[i++] == '-') ? -1 : 1;
        }

        // Read in the digits and check for overflow/underflow condition
        while (i < s.size() && isdigit(s[i])) {
            if (result > INT_MAX / 10 || (result == INT_MAX / 10 && s[i] - '0' > INT_MAX % 10)) {
                return (sign == 1) ? INT_MAX : INT_MIN;
            }
            result = result * 10 + (s[i++] - '0');
        }

        return result * sign;
    }
};

        while (i < s.size() && s[i] == ' ') {
            i++;
        }

Only the space character ' ' is considered a whitespace character.

We skip white spaces using s[i] == ' ' because the above constrain.

        if (i < s.size() && (s[i] == '-' || s[i] == '+')) {
            sign = (s[i++] == '-') ? -1 : 1;
        }

Here, the sign is stored as 1 or -1 and then multiplied by the result. This way, the sign is reflected in the result.

        while (i < s.size() && isdigit(s[i])) {
            if (result > INT_MAX / 10 || (result == INT_MAX / 10 && s[i] - '0' > INT_MAX % 10)) {
                return (sign == 1) ? INT_MAX : INT_MIN;
            }
            result = result * 10 + (s[i++] - '0');
        }

The while loop condition checks if i is less than s.size() and if s[i] is a digit.

If the integer is out of the 32-bit signed integer range [-231, 231 - 1], then clamp the integer so that it remains in the range. Specifically, integers less than -231 should be clamped to -231, and integers greater than 231 - 1 should be clamped to 231 - 1.

We need to return INT_MAX or INT_MIN if result exceeds these limits.

The condition result > INT_MAX / 10 will return INT_MAX or INT_MIN if the result is greater than INT_MAX / 10. This is due to the multiplication of result and 10 in the last line of the condition.

The second condition result == INT_MAX / 10 && s[i] - '0' > INT_MAX % 10 will return INT_MAX or INT_MIN if the result equals INT_MAX / 10 and s[i] is greater than INT_MAX % 10. This is because result * 10 is increased by s[i++] - '0'.

Let's simplify the explanation:

The condition result == INT_MAX / 10 && s[i] - '0' > INT_MAX % 10 is checking if the current number (result) is about to exceed the maximum limit for an integer (INT_MAX).

INT_MAX is the maximum value an integer can hold, which is 2147483647.

The condition result == INT_MAX / 10 is checking if result is equal to the largest possible integer divided by 10, which is 214748364.

The condition s[i] - '0' > INT_MAX % 10 is checking if the current digit of the string (where '0' is subtracted to convert from ASCII to numeric value) is greater than the remainder of INT_MAX divided by 10, which is 7.

If result equals 214748364 (INT_MAX / 10) and the next digit is greater than 7, adding that digit to result would cause it to exceed the maximum value for an integer.

For example, if result is 214748364 and the next digit is 8:

Multiplying result by 10 gives 2147483640.

Adding 8 (the next digit) gives 2147483648.

2147483648 is greater than INT_MAX (2147483647), so it would exceed the limit.

`result == INT_MAX / 10 && s[i] - '0' > INT_MAX % 10`

result == INT_MAX / 10 
result == INT_MAX(2147483647) / 10 
result == 214748364

s[i] - '0' > INT_MAX % 10` 
s[i] - '0' > INT_MAX(2147483647) % 10 
s[i] - '0' > 7

The result will exceed INT_MAX if `result` equals INT_MAX / 10 (214748364) and `s[i] - '0'` is greater than 7.

For instance:
result = 214748364
s[i] = '8'

result * 10 + s[i++] - '0'
2147483640 + 8 
2147483648

The result 2147483648 exceeds INT_MAX.

Solving the 'Reverse Integer' on LeetCode with C++

Shiki Endou — Thu, 20 Jul 2023 10:48:05 +0000

Problem

https://leetcode.com/problems/reverse-integer/description/

Answer

class Solution {
public:
    int reverse(int x) {
        long long result = 0;
        while(x) {
            result = result * 10 + x % 10;
            if (result > INT_MAX || result < INT_MIN) {
                return 0;
            }
            x /= 10;
        }
        return result;
    }
};

Let's examine the solution to the problem.
For an example, consider the following:

Input: x = -123
Output: -321

We solve the problem by taking the last digit in order.

Input: x = -123
1: -3
2: -32
3: -321

Output: -321

Now, let's dissect the code:

    int reverse(int x) {
        long long result = 0;

The long long result = 0 is used to store the answer. It might exceed the int range because we're reversing x. Therefore, we use long long.

        while(x) {
            result = result * 10 + x % 10;

As mentioned before, we solve the problem by taking the last digit in order.

We use x % 10 to get the last digit. The variable result will have a value starting from the second iteration. We use result * 10 to shift the digits one place to the left as we add the new digit to the rightmost place.

x = -123
result = 0
Step 1: result = result * 10 + x % 10 = 0 * 10 + -123 % 10 = -3
x = -12 // explained later in this blog post.
result = -3
Step 2: result = result * 10 + x % 10 = - 3 * 10 + -12 % 10 = -32
x = -1
result = -32
Step 3: result = result * 10 + x % 10 = - 32 * 10 + -1 % 10 = -321

            if (result > INT_MAX || result < INT_MIN) {
                return 0;
            }

If result exceeds the range of int, we must return 0. The condition result > INT_MAX || result < INT_MIN checks for that.

            x /= 10;

We use x /= 10 to eliminate the last digit.

For instance,

x = - 123

Step 1: 
x = -123
// result = 0
result = result * 10 + x % 10 = -3

Step 2: 
x = -12
// result = -3 
result = result * 10 + x % 10 = -3

We need to eliminate the rightmost digit, so we use x /= 10 to shift the digits one place to the right.

We continue this process until x becomes 0.

Solving the 'Zigzag Conversion' on LeetCode with C++

Shiki Endou — Tue, 11 Jul 2023 10:39:49 +0000

Problem

https://leetcode.com/problems/zigzag-conversion/

Answer

class Solution {
public:
    string convert(string s, int numRows) {
        if(numRows == 1) {
            return s;
        }

        vector<string> rows(min(numRows, int(s.size())));
        int currentRow = 0;
        bool goingDown = false;

        int firstRow = 0
        int lastRow = numRows - 1;

        for(char c : s) {
            rows[currentRow] += c;
            if(currentRow == firstRow || currentRow == lastRow) {
                goingDown = !goingDown;
            }
            currentRow += goingDown ? 1 : -1;
        }

        string result;
        for(string row : rows) {
            result += row;
        }

        return result;
    }
};

Let's consider the solution this problem.

Input: s = "PAYPALISHIRING", numRows = 4
Output: "PAHNAPLSIIGYIR"

P   A   H   N
A P L S I I G
Y   I   R

We ask for the answer to combine the strings of each row from the first to the last row.

The first row is "PAHN".
The second row is "APLSIIG".
The third row is "YIR".

"PAHN" + "APLSIIG" + "YIR" = "PAHNAPLSIIGYIR"

Let's write the above algorithm as code.
I repost the answer code.

class Solution {
public:
    string convert(string s, int numRows) {
        if(numRows == 1) {
            return s;
        }

        vector<string> rows(min(numRows, int(s.size())));
        int currentRow = 0;
        bool goingDown = false;

        int firstRow = 0
        int lastRow = numRows - 1;

        for(char c : s) {
            rows[currentRow] += c;
            if(currentRow == firstRow || currentRow == lastRow) {
                goingDown = !goingDown;
            }
            currentRow += goingDown ? 1 : -1;
        }

        string result;
        for(string row : rows) {
            result += row;
        }

        return result;
    }
};

Let's break down the above code.

    string convert(string s, int numRows) {
        if(numRows == 1) {
            return s;
        }

We should return s if numRows is 1 because it's one row.

        vector<string> rows(min(numRows, int(s.size())));
        int currentRow = 0;
        bool goingDown = false;

We need to take the minimum of numRows or the size of input s. Because if numRows is 4 and s has a size of 3, not all rows will be used.

goingDown indicates the moving direction, whether up or down in rows.

        for(char c : s) {
            rows[currentRow] += c;
            if(currentRow == firstRow || currentRow == lastRow) {
                goingDown = !goingDown;
            }
            currentRow += goingDown ? 1 : -1;
        }

rows[currentRow] += c; creates a string for each row.

if(currentRow == firstRow || currentRow == lastRow) {
                goingDown = !goingDown;
            }
            currentRow += goingDown ? 1 : -1;

It reverses goingDown if currentRow is the first row or currentRow is the last row.
It moves currentRow to the next row if goingDown is true.
It moves currentRow to the previous row if goingDown is false`

For example:
The number of rows is 3.

The start currentRow is 0. goingDown is true because rows move from top to bottom.
The next currentRow is 1. goingDown is true and the row still moves from top to bottom because the currentRow is not yet the last row.
The next currentRow is 2. goingDown changes from true to false because the currentRow is the last row. The next currentRow needs to be 1.

string result; for(string row : rows) { result += row; }
It combines the strings of each row.

Solving the 'Longest Palindromic Substring' on LeetCode with C++

Shiki Endou — Tue, 04 Jul 2023 10:28:10 +0000

Problem

https://leetcode.com/problems/longest-palindromic-substring/

Answer

O(N^3)

class Solution { 
private: 
    bool check(string &subString, int subStringSize){
        int i = 0;

        while(i < j) {
            if(subString[i] != subString[j]) {
                return false;
            }
            i++;
            j--;
        }
        return true;
    }

public:
    string longestPalindrome(string s) {
        int inputStringSize = s.size();
        vector<string> substrings;

        for (int i = 0; i < inputStringSize; i++) {
            string tmp = "";

            for (int j = i; j < inputStringSize; j++) {
                tmp += s[j];
                substrings.push_back(tmp);
            }
        }

        int maxLength = 0;
        string longestSubstring = substrings[0];
        int subStringsSize = substrings.size();

        for (int i = 0; i < subStringsSize; i++) {
            int subStringSize = substrings[i].size();

            if(check(substrings[i], subStringSize - 1)){
                if(subStringSize > maxLength){
                    maxLength = subStringSize;
                    longestSubstring = substrings[i];
                }
            }       
        }
        return longestSubstring;
    }
};

Let's consider the solution to this problem.

The problem can be solved by checking all substrings. We determine whether a substring is palindromic by checking if the characters from the head of the substring and the end of the substring, moving towards the middle, are the same.

For instance, let's split the string babd into all possible substrings:
b, ba, bab, babd
ab, abd, bd, d

Now we'll check whether the characters from the head of the substring and the end of the substring are the same, up to the middle of the substring.

For example:
b is a palindromic substring because the first (b) and last (b) characters are the same.
ba is not a palindromic substring because the first (b) and last (a) characters are not the same.
bab is a palindromic substring because the first (b) and last (b) characters are the same.
babd is not a palindromic substring because the first (b) and last (d) characters are not the same.
We continue this process for all substrings.

However, this solution has suboptimal performance because it has a time complexity of O(n^2) for creating all substrings and O(n) for checking whether a substring is palindromic.

There is a solution with time complexity O(n^2) only. Let's explore this solution.

O(N^2)

class Solution {
private: 
    bool solve(vector<vector<bool>> &dp, int startIndex, int endIndex, string &inputString){
        if(startIndex == endIndex){
            return dp[startIndex][endIndex] = true;
        }
        if(endIndex - startIndex == 1){
            if(s[startIndex] == s[endIndex]){
                return dp[startIndex][endIndex] = true;
            }
            else{
                return dp[startIndex][endIndex] = false;
            }
        }
        if(s[startIndex] == s[endIndex] && dp[startIndex + 1][endIndex - 1] == true){
            return dp[startIndex][endIndex] = true;
        } else {
            return dp[startIndex][endIndex] = false;
        }
    }
public:
    string longestPalindrome(string s) {
        int inputStringSize = s.size();
        int startIndexOfMaxLength = 0; int maxLength = 0;
        vector<vector<bool>> dp(inputStringSize, vector<bool>(inputStringSize, false));
        for(int g = 0; g < inputStringSize; g++){
            for(int startIndex = 0, endIndex = g; endIndex < inputStringSize; startIndex++, endIndex++){
                solve(dp, startIndex, endIndex, s);
                if(dp[startIndex][endIndex] == true){
                    if(endIndex - startIndex +　1 > maxLength){
                        startIndexOfMaxLength = startIndex;
                        maxLength = endIndex - startIndex + 1;
                    }
                }
            }
        }
        return inputStringSize.substr(startIndexOfMaxLength, maxLength);
    }
};

This solution use dynamic programming.
It solve a problem that is split to small problem and preserve answer of small problem as memo.

Let's see the inside solution.

    string longestPalindrome(string s) {
        int inputStringSize = s.size();
        int startIndex = 0; int maxLength = 0;
        vector<vector<bool>> dp(inputStringSize, vector<bool>(inputStringSize, false));

inputStringSize variable is length of s that is an argument.
startIndex variable is head index of target string.
maxLength variable is the longest palindrome string.
dp variable is an answer that is preserved small programing as memo and it is preserved an answer as two dimencional array.

Next let's see the solve function that is used in double loop.

    bool solve(vector<vector<bool>> &dp, int startIndex, int endIndex, string &inputString){
        if(startIndex == endIndex){
            return dp[startIndex][endIndex] = true;
        }
        if(endIndex - startIndex == 1){
            if(s[startIndex] == s[endIndex]){
                return dp[startIndex][endIndex] = true;
            }
            else{
                return dp[startIndex][endIndex] = false;
            }
        }
        if(s[startIndex] == s[endIndex] && dp[startIndex + 1][endIndex - 1] == true){
            return dp[startIndex][endIndex] = true;
        } else {
            return dp[startIndex][endIndex] = false;
        }
    }

It assignments true to dp[startIndex][endIndex] if startIndex equals endIndex.
For example:
If startIndex is 0 and endIndex is 0, inputString is one word. It equals palindromic string.

        if(endIndex - startIndex == 1){
            if(s[startIndex] == s[endIndex]){
                return dp[startIndex][endIndex] = true;
            }
            else{
                return dp[startIndex][endIndex] = false;
            }
        }

It assignments true to dp[startIndex][endIndex] if endIndex - startIndex equals 1 and s[StartIndex] equals s[endIndex].
For example:
If s is aa, startIndex is 0 and endIndex is 1, endIndex(1) - startIndex(0) equals 1 and s[0] is a and s[1] is a that equal each other.
It's palindromic string.

It assignments false to dp[startIndex][endIndex] if endIndex - startIndex equals 1 and s[StartIndex] doesn't equal s[endIndex].
For example:
If s is ab, startIndex is 0 and endIndex is 1, endIndex(1) - startIndex(0) equals 1 and s[0] is a and s[1] is b that doesn't equal each other.
It's not palindromic string.

        if(s[startIndex] == s[endIndex] && dp[startIndex + 1][endIndex - 1] == true){
            return dp[startIndex][endIndex] = true;
        } else {
            return dp[startIndex][endIndex] = false;
        }

It assignments true to dp[startIndex][endIndex] if s[startIndex] and s[endIndex] equal and dp[startIndex + 1][endIndex - 1] is true.
For example:
If s is aba, startIndex is 0 and endIndex is 2, s[startIndex] and s[endIndex] equal.
If s is aba and dp[0 + 1][2 - 1] is true, It's palindromic string.
dp[1][1] already is calculated because it is calculated from small substring. dp[1][1] is true because dp[1][1] is b.

It assignments false to dp[startIndex][endIndex] if s[startIndex] and s[endIndex] don't equal or dp[startIndex + 1][endIndex - 1] is not true.
For example:
If s is abcd, startIndex is 0, endIndex is 3 and dp[0 + 1][3 - 1] is false, It's not palindromic string.
dp[1][2] already is calculated because it is calculated from small substring. dp[1][2] is false because dp[1][2] is bc.

        for(int g = 0; g < inputStringSize; g++){
            for(int i = 0, j = g; j < inputStringSize; i++, j++){
                solve(dp, i, j, s);

The loop perform the solve function to all substring from one word to all words.
For example:
inputStringSize is aba.
First, solve(dp, 0, 0, aba). dp[0][0] is true because substring is a.
Second, solve(dp, 1, 1, aba). dp[1][1] is true because substring is b.
Third, solve(dp, 2, 2, aba). dp[2][2] is true because substring is a.

solve(dp, 0, 1, aba). dp[0][1] is false because substring is ab.
solve(dp, 1, 2, aba). dp[1][2] is false because substring is ba.

solve(dp, 0, 2, aba). dp[0][2] is true because substring is aba.

                if(dp[startIndex][endIndex] == true){
                    if(endIndex - startIndex +　1 > maxLength){
                        startIndexOfMaxLength = startIndex;
                        maxLength = endIndex - startIndex + 1;
                    }
                }

It reassignment startIndex to startIndexOfMaxLength and endIndex - startIndex + 1 to maxLength if dp[startIndex][endIndex] that is calculated in the solve function is true and endIndex - startIndex + 1 that is maxLength is bigger than current maxLength.

Finally, longestPalindrome function returns inputStringSize.substr(startIndexOfMaxLength, maxLength) that is the longest palindromic substring.

Solving the 'Longest Substring Without Repeating Characters' problem on LeetCode with C++

Shiki Endou — Tue, 27 Jun 2023 10:19:27 +0000

Problem

https://leetcode.com/problems/longest-substring-without-repeating-characters/

Answer

class Solution {
public:
    int lengthOfLongestSubstring(std::string s) {
        std::unordered_map<char, int> map;
        int maxLength = 0;
        int left = 0;

        for (int right = 0; right < s.length(); right++) {
            if (map.find(s[right]) != map.end()) {
                left = std::max(left, map[s[right]] + 1);
            }

            map[s[right]] = right;
            maxLength = std::max(maxLength, right - left + 1);
        }

        return maxLength;
    }
};

Let's consider the solution to this problem.

The answer is 4 (sapd) when the input is asapda.
We will examine a character from the beginning.
When the first a appears, the length of the longest
substring is 1 (a).

Next, s appears for the first time, extending the length of the longest substring to 2 (as).
Then a appears for the second time. As a already appeared at the beginning of the string, we can't include it in the count.

We are tasked with finding the length of the longest substring without repeating characters. asa would not be the correct answer.

Next we have to start counting characters from the position of s.
This implies that if we encounter a character for the second time, we should start counting from the character following the first occurrence of that character.

Next, p appears for the first time, extending the length of the longest substring to 3 (sap).

Next, d also appears for the first time, extending the length of the longest substring to 4 (sapd).
Last, a appears for the second time, we don't count it.

So the answer is 4 (sapd).

Now, let's consider the above solution in terms of code.
The crucial point is that when a character reappears, we must start counting from the next character in the position in which it last appeared.

We will store the index of a character when we encounter it.
For example with asapda, a is at index 0, s is at index 1.

When a reappears, we need to start counting from the next index after the first a and update the index of a with the new a index.
We don't need to store the index of the same character more than once.

A Map is suitable for this problem because it allows us to store unique key-value pairs. We store a character as the key and its index as the value.

We need to have two variables: the first variable indicates where to start counting and the second variable indicates where to finish counting.

Let's consider the answer code in detail.

        std::unordered_map<char, int> map;
        int maxLength = 0;
        int left = 0;

We declare map as a Map data structure to store a character as the key and its index as the value. The maxLength variable counts the length of the longest substring, and the left variable is indicating where to start counting.

        for (int right = 0; right < s.length(); right++) {

The right variable is that counts characters forward.

            if (map.find(s[right]) != map.end()) {
                left = std::max(left, map[s[right]] + 1);
            }

If we encounter the same character for the second time, we update left, which is the position where we start counting.

However left must not go back from its current position, reassign left to the greater of the current left and the original left.

            map[s[right]] = right;
            maxLength = std::max(maxLength, right - left + 1);
        }

map[s[right]] = right stores a character as the key and its index as the value.

std::max(maxLength, right - left + 1) updates maxLength with the larger of the current maxLength or right (the forward counter) minus left (the start counting position).

We add 1 to ensure accurate character counting because index start from 0.

Solving the 'Add Two Numbers' problem on LeetCode with C++

Shiki Endou — Thu, 22 Jun 2023 10:39:05 +0000

Problem

https://leetcode.com/problems/add-two-numbers/description/

Answer

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* dummy = new ListNode(); 
        ListNode* temp = dummy;
        int carry = 0; 

        while(l1 != NULL || l2 != NULL || carry){ 
            int sum = 0; 
            if(l1 != NULL){
                sum += l1->val; 
                l1 = l1->next; 
            }
            if(l2 != NULL){
                sum += l2->val; 
                l2 = l2->next; 
            }
            sum += carry; 
            carry = sum / 10; 
            ListNode* newnode = new ListNode(sum % 10); 
            temp->next = newnode;
            temp = temp->next; 
        }
        return dummy->next;

Firstly, let's consider the expected output.

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.

We can obtain the output by summing the numbers from l1 and l2 in order.

2 + 5 = 7
4 + 6 = 10 -> 0 // 4 + 6 = 10. Carry 1 to the next digit and truncate the remaining digits. 
3 + 4 = 7 -> 7 + 1 = 8 // Add 1 carried over from the previous digit.

Output: 7, 0, 8

Now we need to represent this operation in the code.

    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* dummy = new ListNode(); 
        ListNode* temp = dummy;
        int carry = 0;

We define dummy as a variable of type ListNode* because the function result is ListNode*.

We define the temp variable to reference the dummy pointer, because we need to reference each node to sum each digit.

We define the carry variable to store the carried over number.

        while(l1 != NULL || l2 != NULL || carry){ 
            int sum = 0; 
            if(l1 != NULL){
                sum += l1->val; 
                l1 = l1->next; 
            }
            if(l2 != NULL){
                sum += l2->val; 
                l2 = l2->next; 
            }

We need to calculate all l1 and l2 numbers.
This means we must continue calculation until l1 and l2 are NULL and carry is 0.

If l1 is not NULL, we add the value of l1 to the sum variable.
We move the l1 pointer to the next pointer because the current l1 value has been calculated.

We do the same for l2.

            sum += carry; 
            carry = sum / 10; 
            ListNode* newnode = new ListNode(sum % 10); 
            temp->next = newnode;
            temp = temp->next; 
        }
        return dummy->next;

If there's a carry from a previous digit, we need to add it to the sum variable and update carry with the new value that needs to be carried over to the next digit.

The first digit of the sum should be assigned to a new Node, and this new Node should be assigned to temp->next.
This adds the new Node to the dummy ListNode, but we don't assign the new Node to dummy->next directly.

Because dummy and temp have same pointer.

The reason for this is that we need to return the head of the new ListNode at the end of the function.

Here, temp is a pointer used for calculating l1 and l2, and dummy is a pointer used to return the head of the new ListNode.

Understanding the Record Type Implementation in TypeScript

Shiki Endou — Wed, 21 Jun 2023 09:35:08 +0000

What is the Record Type in TypeScript?

Firstly, let's talk about the Record feature in TypeScript.

You can find an explanation of the Record type at the following URL:
https://www.typescriptlang.org/docs/handbook/utility-types.html#recordkeys-type

The Record type maps one type to another by accepting two types.

For instance:

type RGBColors = Record<'red' | 'green' | 'blue', number>;

Here, the Record type maps the number type (the second argument) to the union of "red", "green", and "blue" (the first argument).

The result is:

type RGBColors = {
  "red": number;
  "green": number;
  "blue": number;
}

Understanding the Record Type Implementation in TypeScript

You can examine the implementation of the Record type at the following URL:
https://github.com/microsoft/TypeScript/blob/5d8ef4bdcb8bdbd4307c74a07b01e3bdf6e04b6a/lib/lib.es5.d.ts#L1590

/**
 * Construct a type with a set of properties K of type T
 */
type Record<K extends keyof any, T> = {
    [P in K]: T;
};

The Record type accepts two arguments:

The first argument is K extends keyof any, which corresponds to "string" | "number" | "symbol". Hence, the first argument can be of "string" | "number" | "symbol" type.
The second argument, T, is a generic argument. It can accept all types.

Now, let's take a look into the Record type.
The key is [P in K]. The in keyword is used to iterate over K to map P.

For example, when K is "red" | "green" | "blue", [P in K] generates keys that are "red" | "green" | "blue".

Let's revisit the RGBColors type from earlier:

type RGBColors = Record<'red' | 'green' | 'blue', number>;

// This is equivalent to the above RGBColors.
type RGBColors = {
  "red": number;
  "green": number;
  "blue": number;
}

With this explanation, we should now have a better understanding of the Record type in TypeScript.

Solving the 'Two Sum' problem on LeetCode with C++

Shiki Endou — Thu, 15 Jun 2023 14:42:48 +0000

Problem

https://leetcode.com/problems/two-sum/description/?envType=featured-list&envId=top-interview-questions

Answer (Brute Force)

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        for (int i = 0; i < nums.size() - 1; i++) {
            for (int j = i + 1; j < nums.size(); j++) {
                if (nums[i] + nums[j] == target) {
                    return {i, j};
                } 
            }
        }

        return {};
    }
};

To solve this problem, it is necessary to sum each pair of elements in the nums array.

For instance:
nums = [1, 2, 3, 4]
target = 5

1 + 2 = 3;
2 + 3 = 5;
3 + 4 = 7;

As a result, we need to use a double for loop.
The first loop iterates over the nums array up to the second to last element, because we need to sum two elements and thus the last element doesn't need to be included in the first loop.
The second loop starts at position i + 1 to avoid repeating the same combination twice.

Lastly, we return the indices of the two elements in the form of a vector when the sum of these two elements equals the target argument.

In the statement return {i, j}, {i, j} creates a vector containing i and j elements.