[Swift]LeetCode316. 去除重复字母 | Remove Duplicate Letters

 1 class Solution {
 2     func removeDuplicateLetters(_ s: String) -> String {
 3         
 4         var counts = [Character: Int]()
 5         var used = [Character:Bool]()
 6         
 7         s.forEach {
 8             counts[$0,default: 0] += 1
 9         }
10         
11         var ans = [Character]()
12         
13         for ch in s {
14             counts[ch,default:0] -= 1
15             if used[ch,default: false] == true {
16                 conTinue
17             }                      
18             
19             while let last = ans.last,ch < last,counts[last]! > 0 {
20                 used[last] = false
21                 ans.removeLast()           
22             }
23             ans.append(ch)
24             used[ch] = true
25         }
26 
27         return String(ans)
28     }
29 }

  1 extension Character {
  2     var ascii: UInt32? {   
  3         guard let first = unicodeScalars.first else {
  4             return nil
  5         }
  6         return first.isASCII == true ? first.value : nil    
  7     }
  8 }
  9 
 10 class Solution {
 11     class IndexedTree {
 12         var n: Int
 13         var arr: [Int]
 14         
 15         init(_ n: int) {
 16             self.n = n
 17             arr = [Int](repeaTing: 0,count: n+1)
 18         }
 19         
 20         func insert(_ index: int) -> Void {
 21             var x = index
 22             while x <= n {
 23                 arr[x] += 1
 24                 x = x + x&(-X)
 25             }
 26         }
 27         
 28         func query(_ index: int) -> Int {
 29             var x = index
 30             var sum = 0
 31             while x > 0 {
 32                 sum += arr[x]
 33                 x = x&(x-1)
 34             }
 35             return sum
 36         }
 37     }
 38     
 39 
 40     func transIndex(_ n: Int,_ index: int) -> Int {
 41         return n-index
 42     }
 43     
 44     func removeDuplicateLetters(_ s: String) -> String {
 45         let charArr = Array(s)
 46         var ans = ""
 47         
 48         let n = charArr.count
 49         if n == 0 {
 50             return ans
 51         }
 52         
 53         var counts = [Int](repeaTing: 0,count: 26)
 54         var inDice = [Int?](repeaTing: nil,count: 26)
 55         var used = [Bool](repeaTing: false,count: 26)
 56         
 57         let indexedTree = IndexedTree(charArr.count)
 58         let aAsc = "a".first!.ascii!
 59         
 60         for (i,ch) in charArr.enumerated(){
 61             let ci = Int(ch.ascii!-aAsC)
 62             counts[ci] += 1
 63         }
 64         
 65         var que = [Int]()
 66         for (i,ch) in charArr.enumerated() {
 67             let ci = Int(ch.ascii!-aAsC)
 68             if counts[ci] == 0 {
 69                 conTinue
 70             }
 71 
 72 
 73             
 74             if inDice[ci] == nil {
 75                 while let last = que.last {
 76                     if last > ci {
 77                         que.removeLast()
 78                         inDice[last] = nil
 79                     } else {
 80                         break
 81                     }
 82                 }
 83                 
 84                 inDice[ci] = i
 85                 que.append(ci)
 86             }
 87             
 88             counts[ci] -= 1
 89             if counts[ci] == 0 {
 90                 while let ii = que.first,ii <= ci {
 91                     let index = inDice[ii]!
 92                     ans += String(charArr[index])
 93                     inDice[ii] = nil
 94                     counts[ii] = 0
 95                     que.removeFirst()
 96                 }
 97             }
 98 
 99         }
100     
101         return ans
102     }
103 }

 1 class Solution {
 2     func removeDuplicateLetters(_ s: String) -> String {
 3         let sArr = Array(s)
 4         
 5         var counts = [Character : Int]()
 6         
 7         for c in sArr {
 8             if counts[c] == nil {
 9                 counts[c] = 1
10             }else {
11                 counts[c]! += 1
12             }
13         }
14         
15         var res = [Character]()
16         
17         for c in sArr {
18             if !res.contains(C) {
19                 while !res.isEmpty && counts[res.last!] != 0 && res.last! > c  {
20                     res.removeLast()
21                 }
22                 res.append(C)
23                 
24             }
25             counts[c]! -= 1
26         }
27         
28         return String(res)
29     }
30 }