String

String [1/1]

#	✥	Title	Difficulty
1	✅	Valid Palindrome	Easy
2	✅	Count and Say	Easy
3	✅	Flip Game	Easy
4	✅	Implement strStr()	Easy
5	✅	Isomorphic Strings	Easy
6	✅	Reverse String	Easy
7	✅	Reverse Vowels of a String	Easy
8	✅	Length of Last Word	Easy
9	✅	Palindrome Permutation	Easy
10	✅	Valid Anagram	Easy
11	✅	Ransom Note	Easy
12	✅	Group Anagrams	Medium
13	✅	Longest Common Prefix	Easy
14	✅	Longest Substring Without Repeating Characters	Medium
15	✅	One Edit Distance	Medium
16	✅	Word Pattern	Easy
17	✅	Minimum Window Substring	Hard
18	✅	Text Justification	Hard
19	⛔️	Reverse Words in a String	Medium
20	✅	Reverse Words in a String II	Medium
21	✅	Add Strings	Easy
22	⛔️	Multiply Strings	Medium

---

Valid Palindrome

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

For example,
"A man, a plan, a canal: Panama" is a palindrome.
"race a car" is not a palindrome.

Note: Have you consider that the string might be empty? This is a good question to ask during an interview.

For the purpose of this problem, we define empty string as valid palindrome.

Process to lowercased, scan from left and right, skip if not alphanumeric

```swift // Swift class Solution { func isPalindrome(_ s: String) -> Bool { var chars = Array(s.lowercased().characters)

    var left = 0
    var right = chars.count - 1
    while left < right {
        while !chars[left].isAlphanumeric && left < right {
            left += 1
        }
        
        while !chars[right].isAlphanumeric && left < right {
            right -= 1
        }
        
        if chars[left] == chars[right] {
            left += 1
            right -= 1
        } else {
            return false
        }
    }
    
    return true
}

}

extension Character { var value: UInt32? { return String(self).unicodeScalars.first?.value }

// var isAlphanumeric: Bool {
//     guard let value = self.value else { return false }
//     return 
//     ("a".unicodeScalars.first!.value <= value && value <= "z".unicodeScalars.first!.value)
//     ||
//     ("A".unicodeScalars.first!.value <= value && value <= "Z".unicodeScalars.first!.value)
//     ||
//     ("0".unicodeScalars.first!.value <= value && value <= "9".unicodeScalars.first!.value)
// }

var isAlphanumeric: Bool {
    guard let char = String(self).unicodeScalars.first else {
        fatalError("Character is invalid")
    }

    return CharacterSet.alphanumerics.contains(char)
}

}

</p></details>

*****************************************************************************************************************
#### [Count and Say](https://leetcode.com/problems/count-and-say/)
> The count-and-say sequence is the sequence of integers beginning as follows:
1, 11, 21, 1211, 111221, ...

>

1 is read off as "one 1" or 11. 11 is read off as "two 1s" or 21. 21 is read off as "one 2, then one 1" or 1211. Given an integer n, generate the nth sequence.

> **Note**: The sequence of integers will be represented as a string.

<details><summary>Iterate and count</summary><p>
```swift
// Swift
class Solution {
    func countAndSay(_ n: Int) -> String {
		var res = ""
		guard n > 0 else { return res }
		
		res = "1"
		for _ in 1..<n {
			let resChars = [Character](res.characters)
			var nextString = ""
			var lastChar = resChars[0]
			var count = 1
			var j = 1
			while j < resChars.count {
				if resChars[j] == lastChar {
					count += 1
				} else {
					nextString += "\(count)\(lastChar)"
					count = 1
				}
				
				lastChar = resChars[j]
				j += 1
			}
			nextString += "\(count)\(lastChar)"
			res = nextString
		}
		
		return res
	}
}

---

Flip Game

You are playing the following Flip Game with your friend: Given a string that contains only these two characters: + and -, you and your friend take turns to flip two consecutive "++" into "--". The game ends when a person can no longer make a move and therefore the other person will be the winner.

Write a function to compute all possible states of the string after one valid move.

For example, given s = "++++", after one move, it may become one of the following states:
[
  "--++",
  "+--+",
  "++--"
]

If there is no valid move, return an empty list [].

Go through from left to right, if meet two consequent "--", flip

```swift // Swift class Solution { func generatePossibleNextMoves(_ s: String) -> [String] { let chars = [Character](s.characters) var res = [String]() if chars.count <= 1 { return res }

    for i in 0..<chars.count - 1 {
        if chars[i] != chars[i + 1] {
            continue
        }
        if chars[i] == "+" {
            var newStr = String(chars[0..<i]) + "--"
            if i + 2 < chars.count {
                newStr += String(chars[i + 2..<chars.count])
            }
            res.append(newStr)
        }
    }
    return res
}

}

</p></details>

*****************************************************************************************************************
#### [Implement strStr()](https://leetcode.com/problems/implement-strstr/)
> Implement strStr().

> Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

<details><summary>Compare first char, if equals, compare rest</summary><p>
```swift
// Swift
class Solution {
    func strStr(_ haystack: String, _ needle: String) -> Int {
        let haystack = [Character](haystack.characters)
        let needle = [Character](needle.characters)
        
        guard needle.count <= haystack.count else { return -1 }
        
        if haystack.count == 0 { return 0 }
        if needle.count == 0 { return 0 }
        
        for i in 0..<haystack.count {
            // There's no enough characters to compare
            if haystack.count - i < needle.count {
                return -1
            }
            
            // Compare first
            var j = 0
            if needle[j] == haystack[i] {
                var ii = i
                while j < needle.count, ii < haystack.count {
                    if needle[j] == haystack[ii] {
                        j += 1
                        ii += 1
                    } else {
                        break
                    }
                }
                
                if j == needle.count {
                    return i
                }
            }
        }
        
        return -1
    }
}

---

Isomorphic Strings

Given two strings s and t, determine if they are isomorphic.

Two strings are isomorphic if the characters in s can be replaced to get t.

All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character but a character may map to itself.

For example,
Given "egg", "add", return true.
Given "foo", "bar", return false.
Given "paper", "title", return true.

Note: You may assume both s and t have the same length.

Use two hashes, check if key/value matches

```swift // Swift class Solution { func isIsomorphic(_ s: String, _ t: String) -> Bool { let s = [Character](s.characters) let t = [Character](t.characters) guard s.count == t.count else { return false }

	// egg -> add
	// e -> a
	// g -> d
	var map: [Character : Character] = [:]
	var reversedMap: [Character : Character] = [:]
	for i in 0..<s.count {
		if let value = map[s[i]] {
			if value != t[i] { return false }
		} else {
		    // if cannot find skey in map, but find tKey in reversed map
		    // check the reversed key
			if let key = reversedMap[t[i]] {
				if key != s[i] { return false }
			}
			map[s[i]] = t[i]
			reversedMap[t[i]] = s[i]
		}
	}
	return true
}

}

A better way
```swift
// Swift
class Solution {
    func isIsomorphic(_ s: String, _ t: String) -> Bool {
        let s = [Character](s.characters)
		let t = [Character](t.characters)
		if s.count != t.count {
		    return false
		}
		
		var sDict = [Character : Character]()
		var tDict = [Character : Character]()
		
		for i in 0..<s.count {
		    if sDict[s[i]] == nil && tDict[t[i]] == nil {
		        sDict[s[i]] = t[i]
		        tDict[t[i]] = s[i]
		    }
		    else if sDict[s[i]] != t[i] || tDict[t[i]] != s[i] {
		        return false
		    }
		}
		
		return true
    }
}

---

Reverse String

Write a function that takes a string as input and returns the string reversed.

Example:
Given s = "hello", return "olleh".

Straightforward solution

```swift // Swift class Solution { func reverseString(_ s: String) -> String { var s = Array(s.characters) if s.count == 0 { return "" }

     var i = 0
     var j = s.count - 1
     while i < j {
         (s[i], s[j]) = (s[j], s[i])
         i += 1
         j -= 1
     }
     return String(s)
}

}

// Swift
class Solution {
    func reverseString(_ s: String) -> String {
        var s = [Character](s.characters)
		for i in 0..<s.count / 2 {
			(s[i], s[s.count - 1 - i]) = (s[s.count - 1 - i], s[i])
		}
		return String(s)
    }
}

---

Reverse Vowels of a String

Write a function that takes a string as input and reverse only the vowels of a string.

Example 1:
Given s = "hello", return "holle".

Example 2:
Given s = "leetcode", return "leotcede".

Note: The vowels does not include the letter "y".

Get indices of vowels and reverse it

```swift // Swift class Solution { func reverseVowels(_ s: String) -> String { var s = [Character](s.characters) var vowelsIndices: [Int] = []

    for (index, char) in s.enumerated() {
        if char == "a" || char == "e" || char == "i" || char == "o" || char == "u" ||
        char == "A" || char == "E" || char == "I" || char == "O" || char == "U" 
        {
            vowelsIndices.append(index)
        }
    }
    
    for i in 0..<vowelsIndices.count / 2 {
        let left = vowelsIndices[i]
        let right = vowelsIndices[vowelsIndices.count - 1 - i]
        (s[left], s[right]) = (s[right], s[left])
    }
    
    return String(s)
}

}

</p></details>

<details><summary>Use two pointers, left and right, skip if needed. Just like [ValidPalindrome](#valid-palindrome)</summary><p>
```swift
// Swift

---

Length of Last Word

Given a string s consists of upper/lower-case alphabets and empty space characters ' ', return the length of last word in the string.

If the last word does not exist, return 0.

Note: A word is defined as a character sequence consists of non-space characters only.

For example, 
Given s = "Hello World",
return 5.

Split by " ", get last count

```swift // Swift class Solution { func lengthOfLastWord(_ s: String) -> Int { return s.characters.split(separator: " ").last?.count ?? 0 } } ```

Scan from end

```swift // Swift class LengthLastWord { func lengthOfLastWord(s: String) -> Int { var res = 0 var sChars = [Character](s.characters)

    guard sChars.count != 0 else {
        return 0
    }
    
    for i in (0 ... sChars.count - 1).reverse() {
        if res == 0 {
            if sChars[i] == " " {
                continue
            } else {
                res += 1
            }
        } else {
            if sChars[i] == " " {
                break
            } else {
                res += 1
            }
        }
    }
    
    return res
}

}

</p></details>

*****************************************************************************************************************
#### [Palindrome Permutation](https://leetcode.com/problems/palindrome-permutation/)
> Given a string, determine if a permutation of the string could form a palindrome.

>

For example, "code" -> False, "aab" -> True, "carerac" -> True.

> Hint:
- Consider the palindromes of odd vs even length. What difference do you notice?
- Count the frequency of each character.
- If each character occurs even number of times, then it must be a palindrome. How about character which occurs odd number of times?

<details><summary>Calculate word frequency</summary><p>
```swift
// Swift
class Solution {
    func canPermutePalindrome(_ s: String) -> Bool {
		let s = [Character](s.characters)
		var freq: [Character : Int] = [:]
		var oddCount: Int = 0
		
		for i in 0..<s.count {
		    freq[s[i]] = (freq[s[i]] ?? 0) + 1
		}
		
		for (_, value) in freq {
			if value % 2 == 1 {
				oddCount += 1
			}
			
			if oddCount >= 2 {
				return false
			}
		}
		
		return true
	}
}

---

Valid Anagram

Given two strings s and t, write a function to determine if t is an anagram of s.

For example,
s = "anagram", t = "nagaram", return true.
s = "rat", t = "car", return false.

Note: You may assume the string contains only lowercase alphabets.

Follow up: What if the inputs contain unicode characters? How would you adapt your solution to such case?

Sorted and compare

```swift // Swift class Solution { func isAnagram(_ s: String, _ t: String) -> Bool { let s = [Character](s.characters) let t = [Character](t.characters) return s.sorted() == t.sorted() } } ```

---

Ransom Note

Given an arbitrary ransom note string and another string containing letters from all the magazines, write a function that will return true if the ransom note can be constructed from the magazines ; otherwise, it will return false.

Each letter in the magazine string can only be used once in your ransom note.

Note: You may assume that both strings contain only lowercase letters.

canConstruct("a", "b") -> false
canConstruct("aa", "ab") -> false
canConstruct("("aa")", "aab") -> true

Calculate word frequency

```swift // Swift class Solution { func canConstruct(_ ransomNote: String, _ magazine: String) -> Bool { let ransomNote = [Character](ransomNote.characters) let magazine = [Character](magazine.characters)

    var freq: [Character : Int] = [:]
    for i in 0..<magazine.count {
        if let count = freq[magazine[i]] {
            freq[magazine[i]] = count + 1
        } else {
            freq[magazine[i]] = 1
        }
    }
    
    for i in 0..<ransomNote.count {
        if let count = freq[ransomNote[i]] {
            if count == 0 {
                return false 
            }
            freq[ransomNote[i]] = count - 1
        } else {
            return false 
        }
    }
    
    return true
}

}

</p></details>

*****************************************************************************************************************
#### [Group Anagrams](https://leetcode.com/problems/anagrams/)
> Given an array of strings, group anagrams together.

>

For example, given: ["eat", "tea", "tan", "ate", "nat", "bat"], Return: [ ["ate", "eat","tea"], ["nat","tan"], ["bat"] ]

> **Note**: All inputs will be in lower-case.

<details><summary>Use sorted string as key, return values</summary><p>
```swift
// Swift
class Solution {
    func groupAnagrams(_ strs: [String]) -> [[String]] {
        var grouped: [String : [String]] = [:]
        strs.forEach {
            let key = String($0.characters.sorted())
            if let value = grouped[key] {
                grouped[key] = value + [$0]
            } else {
                grouped[key] = [$0]
            }
        }
        
        return Array(grouped.values)
    }
}

---

Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of strings.

Use first string, check each char in rest strings

// Swift
class Solution {
    func longestCommonPrefix1(_ strs: [String]) -> String {
        var res = ""
		guard strs.count > 0 else { return res }
		if strs.count == 1 {
			return strs[0]
		}
		
		let first = strs[0].characters
		for (i, char) in first.enumerated() {
			for j in 1..<strs.count {
				let chars = strs[j].characters
				if i >= chars.count {
					return res
				}
				else if char != chars[chars.index(chars.startIndex, offsetBy: i)] {
					return res
				}
			}
			
			res.append(char)
		}
		
		return res
    }
    
    func longestCommonPrefix(_ strs: [String]) -> String {
        guard strs.count > 0 else {
            return ""
        }
    
        var res = [Character](strs[0].characters)
        
        for str in strs {
            var strContent = [Character](str.characters)
            
            if res.count > strContent.count {
                res = Array(res[0 ..< strContent.count])
            }
            
            for i in 0 ..< res.count {
                if res[i] != strContent[i] {
                    res = Array(res[0 ..< i])
                    break
                }
            }
        }
        
        return String(res)
    }
    
    func longestCommonPrefix2(_ strs: [String]) -> String {
		if strs.count == 0 {
			return ""
		}
		
		if strs.count == 1 {
			return strs[0]
		}
		
		let stringsMaxLength = strs.map { Int($0.characters.count) }.max()!
		
		let stringsMaxIndex = strs.count
		
		var commonPrefix = ""
		
		for checkingIndex in 0 ..< stringsMaxLength {
			var lastChar = ""
			for stringIndex in 0 ..< stringsMaxIndex {
				let string = strs[stringIndex]
				
				if checkingIndex >= string.characters.count {
					return commonPrefix
				}
				
				let char = String(string[string.index(string.startIndex, offsetBy: checkingIndex)])
				
				if lastChar == "" {
					lastChar = char
					continue
				} else if lastChar == char {
					if stringIndex == stringsMaxIndex - 1 {
						commonPrefix += char
					} else {
						continue
					}
				} else {
					return commonPrefix
				}
			}
		}
		
		return commonPrefix
	}
}

---

Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters.

Examples:
Given "abcabcbb", the answer is "abc", which the length is 3.
Given "bbbbb", the answer is "b", with the length of 1.
Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

DP solution

```swift // Swift class Solution { // DP simplified func lengthOfLongestSubstring(_ s: String) -> Int { let chars = Array(s.characters) if chars.count == 0 { return 0 }

    var dict = [Character : Int]() // character to index
    
    var res: Int = 1
    var len: Int = 1
    dict[chars[0]] = 0
    for i in 1..<chars.count {
        if let previousIndex = dict[chars[i]] {
            len = min(len + 1, i - previousIndex)
        }
        else {
            len += 1
        }
        dict[chars[i]] = i
        res = max(res, len)
    }
    
    return res
}

// DP
func lengthOfLongestSubstringDP(_ s: String) -> Int {
    let chars = Array(s.characters)
    if chars.count == 0 {
        return 0
    }
    
    var s = [Int : Int]() // s[i] stands for longest substring ends at index i
    var dict = [Character : Int]() // character to index
    
    s[0] = 1
    dict[chars[0]] = 0
    for i in 1..<chars.count {
        if let previousIndex = dict[chars[i]] {
            s[i] = min(s[i - 1]! + 1, i - previousIndex)
        }
        else {
            s[i] = s[i - 1]! + 1
        }
        dict[chars[i]] = i
    }
    
    return s.values.max()!
}

}

</p></details>

<details><summary>Other historical solutions</summary><p>
```swift
// Swift
class Solution {
    func lengthOfLongestSubstring3(_ s: String) -> Int {
        guard s.isEmpty == false else { return 0 }
		let s = [Character](s.characters)
		var i = 0
		var j = 0
		var dict = [Character : Int]()
		var res = 0
		
		while i < s.count && j < s.count {
		    // If there's existing index and existing index is greater than i
			if let prevJIndex = dict[s[j]], prevJIndex >= i {
				i = max(i, prevJIndex) + 1
			}
			dict[s[j]] = j
			res = max(res, j - i + 1)
			j += 1
		}
		return res
    }
    
    func lengthOfLongestSubstring2(_ s: String) -> Int {
        guard s.isEmpty == false else { return 0 }
        var i = 0
        var j = 0
        let s = [Character](s.characters)
        var res = 0
        
        var set = Set<Character>()
        while i <  s.count && j < s.count {
            if set.contains(s[j]) {
                set.remove(s[i])
                i += 1
            } else {
                set.insert(s[j])
                res = max(res, j - i + 1)
                j += 1
            }
        }
        return res
    }
    
    func lengthOfLongestSubstring1(_ s: String) -> Int {
        guard s.isEmpty == false else { return 0 }
        let s = [Character](s.characters)
        var i = 0
        var j = i + 1
        var max = 1
        var pos: [Character : Int] = [s[0] : 0]
       
        while j < s.count {
            // if find duplicated
            if let existedIndex = pos[s[j]] {
                if s[i] == s[j] {
                    i += 1
                } else {
                    for (k, v) in pos {
                        if v <= existedIndex {
                            pos.removeValue(forKey: k)
                        }
                    }
                    i = existedIndex + 1
                }
            }
            
            if j - i + 1 > max {
                max = j - i + 1
            }
            pos[s[j]] = j
            j += 1
        }
        
        return max
    }
}

---

One Edit Distance

Given two strings S and T, determine if they are both one edit distance apart.

Check for three cases

```swift // Swift class Solution { func isOneEditDistance(_ s: String, _ t: String) -> Bool { let s = Array(s.characters) let t = Array(t.characters)

    if abs(s.count - t.count) > 1 {
        return false
    }
    
    // delete
    // s: a b c  |  a b c
    // t: a   c  |  a b
    if s.count > t.count {
        var p1 = 0
        var p2 = 0
        while p1 < s.count && p2 < t.count {
            if s[p1] != t[p2] {
                if p1 == p2 + 1 {
                    return false
                }
                else {
                    p1 += 1
                    continue
                }
            }
            p1 += 1
            p2 += 1
        }
        return true
    }
    
    // add
    // s: a   b c  |  a b c
    // t: a x b c  |  a b c x
    else if s.count < t.count {
        var p1 = 0
        var p2 = 0
        while p1 < s.count && p2 < t.count {
            if s[p1] != t[p2] {
                if p2 == p1 + 1 {
                    return false
                }
                else {
                    p2 += 1
                    continue
                }
            }
            p1 += 1
            p2 += 1
        }
        return true
    }
    
    // replace
    // s: a x c
    // t: a y c
    else {
        var foundDiff = false
        for i in 0..<s.count {
            if s[i] != t[i] {
                if foundDiff == true {
                    return false
                }
                else {
                    foundDiff = true
                }
            }
        }
        return foundDiff
    }
}

}

</p></details>

<details><summary>Check in one iteration</summary><p>
```swift
// Swift
class Solution {
    func isOneEditDistance(_ s: String, _ t: String) -> Bool {
        let s = Array(s.characters)
        let t = Array(t.characters)
        
        if abs(s.count - t.count) > 1 {
            return false
        }
        
        // delete
        // s: a b c  |  a b c
        // t: a   c  |  a b
        
        // add
        // s: a   b c  |  a b c
        // t: a x b c  |  a b c x
        
        // replace
        // s: a x c
        // t: a y c
        for i in 0..<min(s.count, t.count) {
            if s[i] != t[i] {
                // if not equal, compare rest string
                if s.count > t.count {
                    return s[i + 1..<s.count] == t[i..<t.count]
                }
                else if s.count < t.count {
                    return s[i..<s.count] == t[i + 1..<t.count]
                }
                else {
                    return s[i + 1..<s.count] == t[i + 1..<t.count]
                }
            }
        }
        
        // One string has zero length, difference must be 1
        return abs(s.count - t.count) == 1
    }
}

---

Word Pattern

Given a pattern and a string str, find if str follows the same pattern.

Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in str.

Examples:
pattern = "abba", str = "dog cat cat dog" should return true.
pattern = "abba", str = "dog cat cat fish" should return false.
pattern = "aaaa", str = "dog cat cat dog" should return false.
pattern = "abba", str = "dog dog dog dog" should return false.

Notes: You may assume pattern contains only lowercase letters, and str contains lowercase letters separated by a single space.

Proces two strings to numbered pattern, compare numbered pattern

```swift // Swift class Solution { func wordPattern(_ pattern: String, _ str: String) -> Bool { // Process pattern let pattern = pattern.characters.map { String($0) } // Process str let strs = str.characters.split(separator: " ").map { String($0) }

    return getPattern(pattern) == getPattern(strs)
}

private func getPattern(_ strs: [String]) -> String {
    var dict: [String : Int] = [:]
    var lastValue = 0
    
    strs.forEach {
        if dict[$0] == nil {
            lastValue += 1
            dict[$0] = lastValue
        }
    }
    
    return strs.reduce("") { $0 + String(dict[$1]!) }
}

}

</p></details>

*****************************************************************************************************************
#### [Minimum Window Substring](https://leetcode.com/problems/minimum-window-substring/)
> Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

>

For example, S = "ADOBECODEBANC" T = "ABC" Minimum window is "BANC".

> **Note**:
- If there is no such window in S that covers all characters in T, return the empty string "".
- If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.

<details><summary>Use two pointers to slide window (increase end to find a valid window, decrease start to find the min window), use words frequency dict to help checking whether t is still in the window</summary><p>
```swift
// Swift
class Solution {
    
    // 1. Use two pointers: start and end to represent a window.
    // 2. Move end to find a valid window.
    // 3. When a valid window is found, move start to find a smaller window.
    func minWindow(_ s: String, _ t: String) -> String {
        let s = Array(s.characters)
        let t = Array(t.characters)
        
        // edge case
        if s.count < t.count { return "" }
        
        var start = 0 // window start index
        var end = 0 // window end index (non-inclusive)
        var charsToMatch = t.count // count of chars to match
        var freq = [Character : Int]() // frequency of chars in t
        for char in t {
            if let count = freq[char] {
                freq[char] = count + 1
            }
            else {
                freq[char] = 1
            }
        }
        
        // results
        var windowStart = -1
        var windowLength = Int.max
        
        while end < s.count {
            // move end, to increase window
            if let count = freq[s[end]] {
                // if count to match for this char is postive, decrease charsToMatch
                if count > 0 {
                    charsToMatch -= 1
                }
                
                // char count could be negative, which means duplicated char matched
                freq[s[end]] = count - 1
            }
            
            end += 1
            
            // if now is a valid window (charsToMatch now is 0), move start to decrease start
            while charsToMatch == 0 {
                // Update window if needed
                if windowLength > (end - start) {
                    windowStart = start
                    windowLength = end - start
                }
                
                if let count = freq[s[start]] {
                    freq[s[start]] = count + 1
                    
                    // if char freq is positive, needs to increase charsToMatch
                    if count + 1 > 0 {
                        charsToMatch += 1
                    }
                }
                
                start += 1
            }
        }
        
        if windowStart != -1 {
            return String(s[windowStart..<windowStart + windowLength])
        } else {
            return ""
        }
    }
}

---

Text Justification

Given an array of words and a length L, format the text such that each line has exactly L characters and is fully (left and right) justified.

You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces ' ' when necessary so that each line has exactly L characters.

Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line do not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.

For the last line of text, it should be left justified and no extra space is inserted between words.

For example,
**words**: ["This", "is", "an", "example", "of", "text", "justification."]
**L**: 16.

Return the formatted lines as:
[
   "This    is    an",
   "example  of text",
   "justification.  "
]

Note: Each word is guaranteed not to exceed L in length.

Straightforward solution, needs to be very careful when coding

```swift // Swift class Solution { func fullJustify(_ words: [String], _ maxWidth: Int) -> [String] { var res: [String] = [] guard words.count > 0 else { return res } guard maxWidth > 0 else { return words } var words = words

	// Process words untile it's empty
	while words.isEmpty == false {
		let line = processOneLine(&words, maxWidth)
		res.append(line)
	}
	
	return res
}

private func processOneLine(_ words: inout [String], _ maxWidth: Int) -> String {
	guard words.count > 0 else { return "" }
	
	var pendingWords: [String] = []
	var pendingWordsCount = 0
	while true {
		guard let nextWord = words.first else {
			// no more words to process, this is the last line, left justified
			// Clean trailing space
        	var lastWord = pendingWords.removeLast()
	        lastWord.characters.removeLast()
        	pendingWords.append(lastWord)
            pendingWordsCount -= 1
    
			let extraSpaces = maxWidth - pendingWordsCount
			var spaceString = ""
			for _ in 0..<extraSpaces {
				spaceString += " "
			}
			return pendingWords.joined(separator: "") + spaceString
		}

		if pendingWordsCount + nextWord.characters.count > maxWidth {
			// Cannot process next word, break and start to process this line
			break
		} else {
            // Include next words and continue
            pendingWords.append(nextWord + " ")
            words.removeFirst()
            pendingWordsCount += nextWord.characters.count + 1 // include space
        }
	}

    // Clean trailing space
	pendingWords[pendingWords.count - 1].characters.removeLast()
    pendingWordsCount -= 1
    
    // another way to clean trailing space

// var lastWord = pendingWords.removeLast() // lastWord.characters.removeLast() // pendingWords.append(lastWord)

    // ["a ", "b ", "c"]
    var extraSpaces = maxWidth - pendingWordsCount
    var insertIndex = 0
    while extraSpaces > 0 {
        pendingWords[insertIndex] = pendingWords[insertIndex] + " "
        insertIndex += 1
        if pendingWords.count == 1 {
			insertIndex = 0
		} else {
			insertIndex = insertIndex % (pendingWords.count - 1) // last word has no space
		}
		extraSpaces -= 1
    }

    return pendingWords.joined(separator: "")
}

}

</p></details>

*****************************************************************************************************************
#### [Reverse Words in a String](https://leetcode.com/problems/reverse-words-in-a-string/)
> 

<details><summary>Solution Summary</summary><p>
```swift
// Swift

---

Reverse Words in a String II

Given an input string, reverse the string word by word. A word is defined as a sequence of non-space characters.

The input string does not contain leading or trailing spaces and the words are always separated by a single space.

For example,
Given s = "the sky is blue",
return "blue is sky the".

Could you do it in-place without allocating extra space?

Related problem: Rotate Array

Reverse each word then reverse the whole string

// Java
public class Solution {
    public void reverseWords(char[] s) {
        // step1: reverse each word
        int start = 0;
        for (int i = 0; i < s.length; i++) {
            if (s[i] == ' ') {
                reverse(s, start, i);
                start = i + 1;
            }
            
            // last word has no space
            if (i == s.length - 1) {
                reverse(s, start, i + 1);
            }
        }
        
        // step2: reverse the whole string
        reverse(s, 0, s.length);
    }
    
    public void reverse(char[] s, int from, int to) {
        int left = from;
        int right = to - 1;
        while (left < right) {
            char temp = s[left];
            s[left] = s[right];
            s[right] = temp;
            
            left += 1;
            right -= 1;
        }
    }
}

// Objective-C
+ (void)reverseWords:(NSMutableString *)s
{
	// step1: reverse each word
	NSInteger start = 0;
	for (NSInteger i = 0; i < s.length; i++) {
		if ([[s substringWithRange:NSMakeRange(i, 1)] isEqualTo:@" "]) {
			[self reverse:s from:start to:i];
			start = i + 1;
		}
		
		if (i == s.length - 1) {
			[self reverse:s from:start to:i + 1];
		}
	}
	
	// step2: reverse the whole string
	[self reverse:s from:0 to:s.length];
}

+ (void)reverse:(NSMutableString *)s from:(NSInteger)from to:(NSInteger)to
{
	NSInteger left = from;
	NSInteger right = to - 1;
	while (left < right) {
		NSString *temp = [s substringWithRange:NSMakeRange(left, 1)];
		[s replaceCharactersInRange:NSMakeRange(left, 1)
						 withString:[s substringWithRange:NSMakeRange(right, 1)]];
		[s replaceCharactersInRange:NSMakeRange(right, 1)
						 withString:temp];
		
		left += 1;
		right -= 1;
	}
}

---

Add Strings

Given two non-negative numbers num1 and num2 represented as string, return the sum of num1 and num2.

Note:

• The length of both num1 and num2 is < 5100.
• Both num1 and num2 contains only digits 0-9.
• Both num1 and num2 does not contain any leading zero.
• You must not use any built-in BigInteger library or convert the inputs to integer directly.

Exceed Int limit solution

```swift // Swift // This can exceed limit of integer class Solution { func addStrings(_ num1: String, _ num2: String) -> String { return (num1.integerValue + num2.integerValue).stringValue ?? "" } }

extension String { var integerValue: Int { let chars = Array(self.characters.reversed()) var res = 0 for i in stride(from: chars.count - 1, to: -1, by: -1) { let digit = Int(String(chars[i]))! res = res * 10 + digit } return res } }

extension Int { var stringValue: String? { var reversedString = "" var num = self while num > 0 { let digit = num % 10 reversedString += "(digit)" num /= 10 } if reversedString.isEmpty { return "0" } return String(reversedString.characters.reversed()) } }

</p></details>

<details><summary>Process each char and use carry to calculate sum</summary><p>
```swift
// Swift
class Solution {
    func addStrings(_ num1: String, _ num2: String) -> String {
        let num1 = Array(num1.characters.reversed())
        let num2 = Array(num2.characters.reversed())
        
        var res = ""
        var carry = 0
        
        var i = 0
        while i < num1.count && i < num2.count {
            let sum = Int(String(num1[i]))! + Int(String(num2[i]))! + carry
            let digit = sum % 10
            res += "\(digit)"
            
            carry = sum / 10
            i += 1
        }
        
        let num: [Character]
        if i < num1.count {
            num = num1
        } else {
            num = num2
        }
        
        while i < num.count {
            let sum = Int(String(num[i]))! + carry
            let digit = sum % 10
            res += "\(digit)"
            
            carry = sum / 10
            i += 1
        }
        
        if carry > 0 {
            res += "\(carry)"
        }
        
        return String(res.characters.reversed())
    }
}

---

Multiply Strings

Solution Summary

```swift // Swift ```