Input: board = 
[["5","3",".",".","7",".",".",".","."],
["6",".",".","1","9","5",".",".","."],
[".","9","8",".",".",".",".","6","."],
["8",".",".",".","6",".",".",".","3"],
["4",".",".","8",".","3",".",".","1"],
["7",".",".",".","2",".",".",".","6"],
[".","6",".",".",".",".","2","8","."],
[".",".",".","4","1","9",".",".","5"],
[".",".",".",".","8",".",".","7","9"]]
Output: 
[["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]

import Foundation

class Solution {
    func solveSudoku(_ board: inout [[Character]]) {
        let n = 3
        let N = n * n
        var tracking = Array(repeating: [Character: Int](), count: N * 3)

        func index(_ type: Int, _ i: Int) -> Int { type * N + i }
        func boxIndex(_ r: Int, _ c: Int) -> Int { (r / n) * n + c / n }

        func canPlace(_ num: Character, _ r: Int, _ c: Int) -> Bool {
            let bIdx = boxIndex(r, c)
            return tracking[index(0, r)][num] == nil &&
                   tracking[index(1, c)][num] == nil &&
                   tracking[index(2, bIdx)][num] == nil
        }

        func placeOrRemove(_ num: Character, _ r: Int, _ c: Int, place: Bool) {
            let bIdx = boxIndex(r, c)
            let adjustment = place ? 1 : -1
            tracking[index(0, r)][num, default: 0] += adjustment
            tracking[index(1, c)][num, default: 0] += adjustment
            tracking[index(2, bIdx)][num, default: 0] += adjustment
            board[r][c] = place ? num : "."
        }

        func backtrack(_ r: Int = 0, _ c: Int = 0) {
            if c == N && r == N - 1 { return }
            let nextR = c == N - 1 ? r + 1 : r
            let nextC = c == N - 1 ? 0 : c + 1

            if board[r][c] == "." {
                for num in "123456789" {
                    if canPlace(num, r, c) {
                        placeOrRemove(num, r, c, place: true)
                        backtrack(nextR, nextC)
                        placeOrRemove(num, r, c, place: false)
                    }
                }
            } else {
                backtrack(nextR, nextC)
            }
        }

        for r in 0..<N {
            for c in 0..<N where board[r][c] != "." {
                placeOrRemove(board[r][c], r, c, place: true)
            }
        }

        backtrack()
    }
}

Input
["StreamChecker", "query", "query", "query", "query", "query", "query", "query", "query", "query", "query", "query", "query"]
[[["cd", "f", "kl"]], ["a"], ["b"], ["c"], ["d"], ["e"], ["f"], ["g"], ["h"], ["i"], ["j"], ["k"], ["l"]]
Output
[null, false, false, false, true, false, true, false, false, false, false, false, true]

class TrieNode {
    var children: [Character: TrieNode] = [:]
    var isEndOfWord: Bool = false
}

class StreamChecker {
    private var root: TrieNode = TrieNode()
    private var stream: [Character] = []

    init(_ words: [String]) {
        for word in words {
            var node = root
            for char in word.reversed() {
                if node.children[char] == nil {
                    node.children[char] = TrieNode()
                }
                node = node.children[char]!
            }
            node.isEndOfWord = true
        }
    }

    func query(_ letter: Character) -> Bool {
        stream.insert(letter, at: 0)
        var node = root
        for char in stream {
            if let nextNode = node.children[char] {
                node = nextNode
                if node.isEndOfWord {
                    return true
                }
            } else {
                break
            }
        }
        return false
    }
}

Input: s = "banana"
Output: "ana"

func longestDupSubstring(_ s: String) -> String {
    let arr = Array(s)
    
    func search(_ length: Int) -> String? {
        var seen = Set<String>()
        for i in 0...(arr.count - length) {
            let sub = String(arr[i..<i+length])
            if seen.contains(sub) {
                return sub
            }
            seen.insert(sub)
        }
        return nil
    }

    var left = 1, right = arr.count
    var result = ""
    while left < right {
        let mid = (left + right) / 2
        if let dup = search(mid) {
            result = dup
            left = mid + 1
        } else {
            right = mid
        }
    }
    return result
}

Input
["RLEIterator", "next", "next", "next", "next"]
[[[3, 8, 0, 9, 2, 5]], [2], [1], [1], [2]]
Output
[null, 8, 8, 5, -1]

class RLEIterator {
    private var encoding: [Int]
    private var index: Int

    init(_ encoding: [Int]) {
        self.encoding = encoding
        self.index = 0
    }

    func next(_ n: Int) -> Int {
        var n = n
        while index < encoding.count {
            if n > encoding[index] {
                n -= encoding[index]
                index += 2
            } else {
                encoding[index] -= n
                return encoding[index + 1]
            }
        }
        return -1
    }
}

Input: num1 = "2", num2 = "3"
Output: "6"

func addStrings(_ num1: [Int], _ num2: [Int]) -> [Int] {
    var ans = [Int]()
    var carry = 0
    let maxLength = max(num1.count, num2.count)

    for i in 0..<maxLength {
        let digit1 = i < num1.count ? num1[i] : 0
        let digit2 = i < num2.count ? num2[i] : 0

        let sum = digit1 + digit2 + carry
        carry = sum / 10
        ans.append(sum % 10)
    }

    if carry > 0 {
        ans.append(carry)
    }
    return ans
}

func multiplyOneDigit(_ firstNumber: [Int], _ secondNumberDigit: Int, _ numZeros: Int) -> [Int] {
    var currentResult = Array(repeating: 0, count: numZeros)
    var carry = 0

    for digit in firstNumber {
        let multiplication = secondNumberDigit * digit + carry
        carry = multiplication / 10
        currentResult.append(multiplication % 10)
    }

    if carry > 0 {
        currentResult.append(carry)
    }
    return currentResult
}

func multiply(_ num1: String, _ num2: String) -> String {
    if num1 == "0" || num2 == "0" {
        return "0"
    }

    let firstNumber = Array(num1).reversed().map { Int(String($0))! }
    let secondNumber = Array(num2).reversed().map { Int(String($0))! }

    var ans = Array(repeating: 0, count: firstNumber.count + secondNumber.count)

    for (i, digit) in secondNumber.enumerated() {
        let partialResult = multiplyOneDigit(firstNumber, digit, i)
        ans = addStrings(ans, partialResult)
    }

    while ans.last == 0 && ans.count > 1 {
        ans.removeLast()
    }

    return ans.reversed().map { String($0) }.joined()
}

Input: n = 4

Output: "1211"

Explanation:

countAndSay(1) = "1"
countAndSay(2) = RLE of "1" = "11"
countAndSay(3) = RLE of "11" = "21"
countAndSay(4) = RLE of "21" = "1211"

func countAndSay(_ n: Int) -> String {
    var s = "1"
    for _ in 2...n {
        var t = ""
        var matches = Array(s.matchingStrings(regex: "(.)\\1*"))
        for match in matches {
            t += "\(match[0].count)\(match[1])"
        }
        s = t
    }
    return s
}

extension String {
    func matchingStrings(regex: String) -> [[String]] {
        do {
            let regex = try NSRegularExpression(pattern: regex)
            let results = regex.matches(in: self, range: NSRange(self.startIndex..., in: self))
            return results.map { result in
                (0..<result.numberOfRanges).map {
                    String(self[Range(result.range(at: $0), in: self)!])
                }
            }
        } catch let error {
            print("invalid regex: \(error.localizedDescription)")
            return []
        }
    }
}

Input: s = "1101"
Output: 6
Explanation: "1101" corressponds to number 13 in their decimal representation.
Step 1) 13 is odd, add 1 and obtain 14. 
Step 2) 14 is even, divide by 2 and obtain 7.
Step 3) 7 is odd, add 1 and obtain 8.
Step 4) 8 is even, divide by 2 and obtain 4.  
Step 5) 4 is even, divide by 2 and obtain 2. 
Step 6) 2 is even, divide by 2 and obtain 1.  

class Solution {
    func numSteps(_ s: String) -> Int {
        var str = Array(s)
        var operations = 0

        while str.count > 1 {
            if str.last == "0" {
                str.removeLast()
            } else {
                var i = str.count - 1
                while i >= 0 && str[i] == "1" {
                    str[i] = "0"
                    i -= 1
                }
                if i < 0 {
                    str.insert("1", at: 0)
                } else {
                    str[i] = "1"
                }
            }
            operations += 1
        }

        return operations
    }
}

Input
["FindElements","find","find"]
[[[-1,null,-1]],[1],[2]]
Output
[null,false,true]

class TreeNode {
    var val: Int
    var left: TreeNode?
    var right: TreeNode?
    init(_ val: Int) { 
        self.val = val 
        self.left = nil
        self.right = nil
    }
}

class FindElements {
    private var root: TreeNode?
    private var values: Set<Int>
    
    init(_ root: TreeNode?) {
        self.root = root
        self.values = Set<Int>()
        if let root = root {
            root.val = 0
            values.insert(0)
            recover(root)
        }
    }
    
    private func recover(_ node: TreeNode) {
        if let left = node.left {
            left.val = 2 * node.val + 1
            values.insert(left.val)
            recover(left)
        }
        if let right = node.right {
            right.val = 2 * node.val + 2
            values.insert(right.val)
            recover(right)
        }
    }
    
    func find(_ target: Int) -> Bool {
        return values.contains(target)
    }
}

Input: graph = [[1,2,3],[0,2],[0,1,3],[0,2]]
Output: false
Explanation: There is no way to partition the nodes into two independent sets such that every edge connects a node in one and a node in the other.

class Solution {
    func isBipartite(_ graph: [[Int]]) -> Bool {
        var color = [Int: Int]()
        for node in 0..<graph.count {
            if color[node] == nil {
                var stack = [node]
                color[node] = 0
                while !stack.isEmpty {
                    let node = stack.removeLast()
                    for nei in graph[node] {
                        if color[nei] == nil {
                            stack.append(nei)
                            color[nei] = color[node]! ^ 1
                        } else if color[nei] == color[node] {
                            return false
                        }
                    }
                }
            }
        }
        return true
    }
}

Input: nums = [3,5,2,6], k = 2
Output: [2,6]
Explanation: Among the set of every possible subsequence: {[3,5], [3,2], [3,6], [5,2], [5,6], [2,6]}, [2,6] is the most competitive.

class Solution {
    func mostCompetitive(_ nums: [Int], _ k: Int) -> [Int] {
        var queue = [Int]()
        var additionalCount = nums.count - k
        
        for num in nums {
            while !queue.isEmpty && queue.last! > num && additionalCount > 0 {
                queue.removeLast()
                additionalCount -= 1
            }
            queue.append(num)
        }
        
        return Array(queue.prefix(k))
    }
}

Input: synonyms = [["happy","joy"],["sad","sorrow"],["joy","cheerful"]], text = "I am happy today but was sad yesterday"
Output: ["I am cheerful today but was sad yesterday","I am cheerful today but was sorrow yesterday","I am happy today but was sad yesterday","I am happy today but was sorrow yesterday","I am joy today but was sad yesterday","I am joy today but was sorrow yesterday"]

class Solution {
    func generateSentences(_ synonyms: [[String]], _ text: String) -> [String] {
        var graph = [String: Set<String>]()

        for pair in synonyms {
            graph[pair[0], default: Set()].insert(pair[1])
            graph[pair[1], default: Set()].insert(pair[0])
        }

        let words = text.split(separator: " ").map { String($0) }
        var synonymGroups = [[String]]()
        for word in words {
            synonymGroups.append(findSynonyms(graph, word))
        }

        var sentences = [String]()
        var sentence = ""
        generate(&sentences, synonymGroups, &sentence, 0)
        return sentences.sorted()
    }

    private func findSynonyms(_ graph: [String: Set<String>], _ word: String) -> [String] {
        var synonyms = Set<String>()
        var stack = [word]
        while !stack.isEmpty {
            let w = stack.removeLast()
            if synonyms.insert(w).inserted {
                for neighbor in graph[w] ?? [] {
                    stack.append(neighbor)
                }
            }
        }
        return Array(synonyms).sorted()
    }

    private func generate(_ sentences: inout [String], _ groups: [[String]], _ sentence: inout String, _ index: Int) {
        if index == groups.count {
            sentences.append(sentence.trimmingCharacters(in: .whitespaces))
            return
        }
        for word in groups[index] {
            let original = sentence
            sentence += " " + word
            generate(&sentences, groups, &sentence, index + 1)
            sentence = original
        }
    }
}

Input: nums = [4,2,3]
Output: true
Explanation: You could modify the first 4 to 1 to get a non-decreasing array.

class Solution {
    func checkPossibility(_ nums: [Int]) -> Bool {
        var nums = nums
        var count = 0
        
        for i in 1..<nums.count {
            if nums[i] < nums[i - 1] {
                if count > 0 {
                    return false
                }
                count += 1
                if i == 1 || nums[i] >= nums[i - 2] {
                    nums[i - 1] = nums[i]
                } else {
                    nums[i] = nums[i - 1]
                }
            }
        }
        
        return true
    }
}

Input: root1 = [2,1,4], root2 = [1,0,3]
Output: [0,1,1,2,3,4]

class TreeNode {
    var val: Int
    var left: TreeNode?
    var right: TreeNode?
    init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
}

class Solution {
    func getAllElements(_ root1: TreeNode?, _ root2: TreeNode?) -> [Int] {
        var stack1 = [TreeNode](), stack2 = [TreeNode]()
        var output = [Int]()
        var root1 = root1
        var root2 = root2

        while root1 != nil || root2 != nil || !stack1.isEmpty || !stack2.isEmpty {
            while root1 != nil {
                stack1.append(root1!)
                root1 = root1!.left
            }
            while root2 != nil {
                stack2.append(root2!)
                root2 = root2!.left
            }
            if stack2.isEmpty || (!stack1.isEmpty && stack1.last!.val <= stack2.last!.val) {
                root1 = stack1.removeLast()
                output.append(root1!.val)
                root1 = root1!.right
            } else {
                root2 = stack2.removeLast()
                output.append(root2!.val)
                root2 = root2!.right
            }
        }
        return output
    }
}

Input: words = ["ab","bc"], s = "aabcd"
Output: "a<b>abc</b>d"

func addBoldTags(_ keywords: [String], _ s: String) -> String {
    var bold = Array(repeating: false, count: s.count)
    let sArray = Array(s)
    
    for word in keywords {
        var start = s.range(of: word)
        while start != nil {
            let range = start!.lowerBound..<s.index(start!.lowerBound, offsetBy: word.count)
            for i in range {
                bold[s.distance(from: s.startIndex, to: i)] = true
            }
            start = s.range(of: word, range: range.upperBound..<s.endIndex)
        }
    }
    
    var result = ""
    var i = 0
    while i < s.count {
        if bold[i] {
            result += "<b>"
            while i < s.count && bold[i] {
                result.append(sArray[i])
                i += 1
            }
            result += "</b>"
        } else {
            result.append(sArray[i])
            i += 1
        }
    }
    
    return result
}

Input: clips = [[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]], time = 10
Output: 3

class Solution {
    func videoStitching(_ clips: [[Int]], _ T: Int) -> Int {
        let clips = clips.sorted { $0[0] < $1[0] || ($0[0] == $1[0] && $0[1] > $1[1]) }
        var end = -1, end2 = 0, res = 0
        
        for clip in clips {
            if end2 >= T || clip[0] > end2 {
                break
            } else if end < clip[0] && clip[0] <= end2 {
                res += 1
                end = end2
            }
            end2 = max(end2, clip[1])
        }
        return end2 >= T ? res : -1
    }
}

Input: arr = [1,5,7,8,5,3,4,2,1], difference = -2
Output: 4
Explanation: The longest arithmetic subsequence is [7,5,3,1].

class Solution {
    func longestSubsequence(_ arr: [Int], _ difference: Int) -> Int {
        var dp = [Int: Int]()
        var answer = 1
        
        for a in arr {
            let beforeA = dp[a - difference, default: 0]
            dp[a] = beforeA + 1
            answer = max(answer, dp[a]!)
        }
        
        return answer
    }
}

Input: nums1 = [2,7,11,15], nums2 = [1,10,4,11]
Output: [2,11,7,15]

class Solution {
    func advantageCount(_ A: [Int], _ B: [Int]) -> [Int] {
        let sortedA = A.sorted()
        let sortedB = B.enumerated().sorted { $0.element < $1.element }
        var assigned = [Int: [Int]]()
        var remaining = [Int]()
        
        var j = 0
        for a in sortedA {
            if a > sortedB[j].element {
                assigned[sortedB[j].element, default: []].append(a)
                j += 1
            } else {
                remaining.append(a)
            }
        }
        
        var result = [Int]()
        for b in B {
            if let val = assigned[b]?.popLast() {
                result.append(val)
            } else {
                result.append(remaining.popLast()!)
            }
        }
        return result
    }
}

Input: arr = [1,1,2,2,3,3,4,4,5,5], target = 8
Output: 20

class Solution {
    func minMalwareSpread(_ graph: [[Int]], _ initial: [Int]) -> Int {
        func dfs(_ node: Int, _ infected: inout Set<Int>) {
            for neighbor in 0..<graph.count {
                if graph[node][neighbor] == 1 && !infected.contains(neighbor) {
                    infected.insert(neighbor)
                    dfs(neighbor, &infected)
                }
            }
        }

        let n = graph.count
        var initialSet = Set(initial)
        let sortedInitial = initial.sorted()
        var minInfected = Int.max
        var bestNode = sortedInitial[0]
        
        for node in sortedInitial {
            var infected = initialSet
            infected.remove(node)
            for i in initialSet {
                if i != node {
                    dfs(i, &infected)
                }
            }
            if infected.count < minInfected {
                minInfected = infected.count
                bestNode = node
            }
        }
        
        return bestNode
    }
}