String

Longest Substring Without Repeating Characters

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

Code:

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int[] chars = new int[128];
        int n = s.length();
        int res = 0, len = 0;
        int left = 0, right = 0;
        while (right < n) {
            char c = s.charAt(right);
            chars[c]++;
            while (chars[c] > 1) {
                char l = s.charAt(left);
                chars[l]--;
                left++;
            }
            len = right - left + 1;
            res = Math.max(res, len);
            right++;
        }
        return res;
    }
}

• Sliding Window;

• Time complexity: O(n);

• charAt() method for string;

• length() method for string;

Longest Palindromic Substring

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

Code:

class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        String res = "";
        boolean[][] dp = new boolean[n][n];
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                boolean sb = s.charAt(i) == s.charAt(j);
                dp[i][j] = sb && (j - i < 3 || dp[i+1][j-1]);
                if (dp[i][j] && (j - i + 1 > res.length())) {
                    res = s.substring(i, j+1);
                }
            }
        }
        return res;
    }
}

• Dynamic programming;

• Time complexity: O(n^2);

• Note the i loop is from n-1 to 0, because the transition function needs to know dp[i+1][j-1] first;

• substring() method for string: to include the last character, substring(i, j+1);

Merge Strings Alternately

Link: https://leetcode.com/problems/merge-strings-alternately/

class Solution:
    def mergeAlternately(self, word1: str, word2: str) -> str:
        merged_str = ""
        length1, length2 = len(word1), len(word2)
        min_length = min(length1, length2)
        for i in range(min_length):
            merged_str = merged_str + word1[i] + word2[i]
        if length1 < length2:
            merged_str += word2[length1:]
        if length1 > length2:
            merged_str += word1[length2:]
        return merged_str

• Time complexity: O(n).

Reverse Words in a String

Link: https://leetcode.com/problems/reverse-words-in-a-string/

class Solution:
    def reverseWords(self, s: str) -> str:
        s = s.strip()
        words = s.split(" ")
        reversed = ""
        for word in words[::-1]:
            if word:
                reversed += word.strip()
                reversed += " "
        reversed = reversed[:-1]
        return reversed

• Time complexity: O(n).

• strip() method for string: remove leading and trailing spaces;

• split() method for string: split string by a delimiter;

• join() method for string: join a list of strings by a delimiter;

• [::-1] for list: reverse a list;

• [:-1] for list: remove the last element of a list;

• if word:: check if a string is empty;

Greatest Common Divisor of Strings

Link: https://leetcode.com/problems/greatest-common-divisor-of-strings/

class Solution:
    def gcdOfStrings(self, str1: str, str2: str) -> str:
        if str1 + str2 != str2 + str1:
            return ""
        max_length = gcd(len(str1), len(str2))
        return str1[:max_length]

Let m,n be the lengthes of the two input strings str1 and str2.

• Time complexity: O(m+n)

  • We need to compare the two concatenations of length O(m+n), it takes O(m+n) time.

  • We calculate the GCD using binary Euclidean algorithm, it takes log⁡(m⋅n) time.

  • To sum up, the overall time complexity is O(m+n).

• Space complexity: O(m+n)

  • We need to compare the two concatenations of length O(m+n).