763. Partition Labels.md

763. Partition Labels

---

leetcode Daily Challenge on September 4th, 2020.

leetcode-cn Daily Challenge on October 22th, 2020.

---

Difficulty : Medium

Related Topics : Two Pointers、Greedy

---

A string S of lowercase English letters is given. We want to partition this string into as many parts as possible so that each letter appears in at most one part, and return a list of integers representing the size of these parts.

Example 1:

Input: S = "ababcbacadefegdehijhklij"
Output: [9,7,8]
Explanation:
The partition is "ababcbaca", "defegde", "hijhklij".
This is a partition so that each letter appears in at most one part.
A partition like "ababcbacadefegde", "hijhklij" is incorrect, because it splits S into less parts.

Note:

• S will have length in range [1, 500].
• S will consist of lowercase English letters ('a' to 'z') only.

---

Solution

• mine
  • Java
    • Runtime: 2 ms, faster than 99.66%, Memory Usage: 38.2 MB, less than 73.50% of Java online submissions

      //O(N)time
      //O(N)space
      public List<Integer> partitionLabels(String S) {
          List<Integer> res = new LinkedList<>();
      
          char[] arr = S.toCharArray();
          int n = arr.length;
          if(n == 0) return res;
      
          //record the char last index
          int[] t = new int[26];
          for(int i = 0; i < n; i++){
              t[arr[i] - 'a'] = i;
          }
          //get the first char max index
          int max = t[arr[0] - 'a'];
          //the substring start index
          int s = 0;
          for(int i = 0; i < n;i++){
              if(i == max){
                  //i == max is mean we got a require substring
                  res.add(max - s + 1);
                  s = max + 1;
                  if(i + 1 < n){
                      max = t[arr[i + 1] - 'a'];
                  }
              }else{
                  //find the max index of char in [s, max]
                  max = Math.max(t[arr[i] - 'a'], max);
              }
          }
          return res;
      }
      

---

• the most votes

• Runtime: 3 ms, faster than 90.58%, Memory Usage: 38 MB, less than 84.57% of Java online submissions

  //O(N)time
  //O(1)space
  public List<Integer> partitionLabels(String S) {
      if(S == null || S.length() == 0){
          return null;
      }
      List<Integer> list = new ArrayList<>();
      int[] map = new int[26];  // record the last index of the each char
  
      for(int i = 0; i < S.length(); i++){
          map[S.charAt(i)-'a'] = i;
      }
      // record the end index of the current sub string
      int last = 0;
      int start = 0;
      for(int i = 0; i < S.length(); i++){
          last = Math.max(last, map[S.charAt(i)-'a']);
          if(last == i){
              list.add(last - start + 1);
              start = last + 1;
          }
      }
      return list;
  }
  

---