Given a string, find the longest substring which contains 2 unique characters. ""abcbbbbcccbdddadacb" = "bcbbbbcccb"

Question

Given a string, find the longest substring which contains 2 unique characters. ""abcbbbbcccbdddadacb" => "bcbbbbcccb"

Jageloo Yadav · Accepted Answer

Can be easily achieved  by  below 2 functions

/// Calculate unique array
func getUniqe(uniqueChars: [Character]) -> [Character] {
    var sdd: [Character] = []
    for s in uniqueChars {
        if !sdd.contains(s) {
            sdd.append(s)
        }
    }
    return sdd
}

func findLongestSubstringContainsTwoUniqueCharacters(input: String = "abcbbbbcccbdddadacb") -> String {
    var inputChars = [Character].init(input)
    var result: [Character] = []
    for indexi in 0.. indexi {
                let charOuter = inputChars[indexo]
                appends.append(charOuter)
                if getUniqe(uniqueChars: appends).count == 2 && appends.count > result.count {
                    result = appends
                }
            }
        }
    }
    return String(result)
}

print(findLongestSubstringContainsTwoUniqueCharacters())

Sigiloso · Answer

func longestString(_ input: String) -> String {
    let chars = input.compactMap({ $0 })
    var array: [Character] = []
    var string = ""
    for (_, char) in chars.enumerated() {
        let set = Set((array + [char]))
        print(set)
        if set.count > 2 {
            let temp = String(array)
            if temp.count > string.count {
                string = String(array)
            }
            array.removeFirst()
        }
        array.append(char)
    }
    return string
}
print(longestString("abcbbbbcccbdddadacb"))

Not sure about efficiency but this works well · Answer

extension String {
    var uniqueCharList:[Character] {
        let characterSet: Set = Set.init(Array(self[self.startIndex...]))
        
        print("\(characterSet)")
        return Array(characterSet)
    }
    
    func removeFirstRepeatingChar() -> String {
        var copy = self
        while copy.uniqueCharList.count > 1 {
            copy = String(copy.dropFirst())
        }
        print("repeadingCharacter: \(copy)")
        return copy
    }
}

func findLargestSubstring( _ input: String) -> String {
    
    var subStringList:[String] = [String]()
    var subString = ""
    for i in input {
        subString.append(i)
        
        let subStringUniqueCharList = subString.uniqueCharList
        if subStringUniqueCharList.count > 2{
            subString = String(subString.dropLast())
            subStringList.append(subString)
            subString = subString.removeFirstRepeatingChar()
            subString.append(i)
        }
        else {
            subStringList.append(subString)
        }
    }
    
    subStringList.sort { $0.count < $1.count }
    print("\(subStringList)")
    return subStringList.last ?? ""
    
}

Here is another one optimized solution. Please comment if there is any even more optimized solution · Answer

extension Dictionary where Value: Equatable {
    func findKey(_ value: Value) -> Key? {
        return first(where: { return $1 == value })?.key }
}

func findLargestV2(_ input: String, _ maxCharCount: Int) -> String {
    
    var dict:[String: Int] = [String : Int] ()
    var max_len = 0
    var lowestIndex = 0
    var min_Index = 0
    for (index, char) in input.enumerated() {
        dict[String(char)] = index
        
        if dict.count > maxCharCount {
            if let minIndex = dict.values.min() {
                min_Index = minIndex
                if let key = dict.findKey(minIndex) {
                    dict.removeValue(forKey: key)
                }
                lowestIndex = minIndex + 1
            }
        }
        max_len = max(index - lowestIndex + 1, max_len)
    }
    
    let minIndex = input.index(input.startIndex, offsetBy: lowestIndex)
    let lastIndex = input.index(minIndex, offsetBy: max_len)
    let subString = String(input[minIndex..

Viren · Answer

func longestString(_ input: String) -> String {
    let chars = input.compactMap({ $0 })
    var array: [Character] = []
    var string = ""
    for char in chars {
        let set = Set((array + [char]))
        if set.count > 2 {
            let temp = String(array)
            if temp.count > string.count {
                string = String(array)
            }
            array.removeFirst()
        }
        array.append(char)
    }
    return string
}
print(longestString("abcbbbbcccbdddadacb"))

Jeremy · Answer

func findLongestSubstringWithTwoCharacters(input: String) -> String {
    var currentSubstring:String?
    var longestSubString = ""
    var firstLetter:String?
    var secondLetter:String?
    let letterArray = input.map { String($0) }
    
    for letter in letterArray {
        if let cur = currentSubstring {
            if let first = firstLetter, let second = secondLetter {
                if letter == first || letter == second {
                    currentSubstring = cur + letter
                } else {
                    if longestSubString.count < cur.count {
                        longestSubString = cur
                    }
                    
                    firstLetter = second
                    secondLetter = letter
                    currentSubstring = firstLetter! + secondLetter!
                }
            } else if let first = firstLetter {
                if first == letter {
                    currentSubstring = cur + first
                } else {
                    secondLetter = letter
                }
            }
        } else {
            currentSubstring = letter
            firstLetter = letter
        }
    }
    
    if let cur = currentSubstring, longestSubString.count < cur.count {
        longestSubString = cur
    }
    
    return longestSubString
}

Google

Pergunta de entrevista da empresa Google

Respostas da entrevista

Empresas seguidas

Buscas de vagas