leetCodeString.swift

// 5. Longest Palindromic Substring
// Link: https://leetcode.com/problems/longest-palindromic-substring/
// Time O(n^2), Space O(1)
var maxLength = 0
var firstIndex = 0
func longestPalindrome(_ s: String) -> String {

    if s.count < 2 { return s }
    let sArray = Array(s)
    for i in 0..<sArray.count-1 {
        checkPalindrome(sArray, i, i)
        checkPalindrome(sArray, i, i+1)
    }
    let startIndex = s.index(s.startIndex, 
                             offsetBy: firstIndex)
    let endIndex = s.index(s.startIndex, 
                             offsetBy: firstIndex + maxLength)


    return String(s[startIndex..<endIndex])
}

func checkPalindrome(_ chars: [Character], _ left: Int, _ right: Int) {
    var l = left
    var r = right

    while l >= 0 && r < chars.count && chars[l] == chars[r] {
            l -= 1
            r += 1
    }

    if r - l - 1 > maxLength { 
        maxLength = r - l - 1 
        firstIndex = l + 1
    }
}


// 424. Longest Repeating Character Replacement
// Time O(n), Space: O(n)
func characterReplacement(_ s: String, _ k: Int) -> Int {
    var sArray = Array(s)
    var maxLength = 0
    var charCount = [Character: Int]()
    var maxCount = 0
    var start = 0
    var end = 0

    for end in 0..<sArray.count {
        let newCount = charCount[sArray[end], default: 0] + 1
        charCount[sArray[end]] = newCount
        maxCount = max(maxCount, newCount)

        if end - start + 1 - maxCount > k {
            charCount[sArray[start]] = charCount[sArray[start]]! - 1
            start += 1
        }

        maxLength = max(maxLength, end - start + 1)
    }

    return maxLength
}



// 3. Longest Substring Without Repeating Characters
// https://leetcode.com/problems/longest-substring-without-repeating-characters/
// Time: O(n), Space: O(n)
func lengthOfLongestSubstring(_ s: String) -> Int {
    let sArray = Array(s)
    var maxLength = 0
    var charToIndex = [Character : Int]()
    var start = 0
    for end in 0..<s.count {
        let charIndex = charToIndex[sArray[end], default: -1]
        if charIndex != -1 {
            start = max(start, charIndex + 1)       
        } 
        maxLength = max(maxLength, end - start + 1)
        charToIndex[sArray[end]] = end
    }

    return maxLength
}


// 76. Minimum Window Substring
// https://leetcode.com/problems/minimum-window-substring/
// Time O(S + T), Space O(S + T)
func minWindow(_ s: String, _ t: String) -> String {
    var sArray = Array(s)
    var dict = [Character: Int]()
    var start = 0, end = 0, minStart = 0, minLen = Int.max, counter = t.count

    for char in t { 
        dict[char] = dict[char, default: 0] + 1 
    }

    while end < sArray.count {
        if let freq = dict[sArray[end]] {
            if freq > 0 { counter -= 1 }
            dict[sArray[end]] = freq - 1

            while counter == 0 { // found all characters
                if end - start < minLen { minLen = end - start; minStart = start }
                if let startFreq = dict[sArray[start]] { 
                    if startFreq == 0 { counter += 1 }
                    dict[sArray[start]] = startFreq + 1
                }
                start += 1
            }
        }
        end += 1
    }

    return minLen == Int.max ? "" : String(sArray[minStart...minStart + minLen])
}



// https://leetcode.com/problems/palindromic-substrings
// Time n^2, Space 1
func countSubstrings(_ s: String) -> Int {
    let sArray = Array(s)
    var count = sArray.count
    for i in 0..<sArray.count - 1 {
        count += countPalindrome(i, i + 1, sArray)
        count += countPalindrome(i - 1, i + 1, sArray)
    }

    return count
}

func countPalindrome(_ l: Int, _ r: Int, _ arr: [Character]) -> Int {
    var left = l, right = r
    var count = 0
    while left  >= 0 && right < arr.count  && arr[left] == arr[right] {
        count += 1
        left -= 1
        right += 1
    }
    return count
}