# String

### Longest Substring Without Repeating Characters

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

Code:

```java
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:

```java
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/>

```python
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/>

```python
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/>

```python
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).


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://jinjunliu.gitbook.io/notes/leetcode/8.2_string.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.