{"size": 1630, "ext": "js", "max_stars_repo_path": "leetcode/L0750/lc763.js", "max_stars_repo_name": "brianshen1990/KeepLearning", "max_stars_repo_stars_event_min_datetime": "2021-02-23T07:42:31.000Z", "max_stars_repo_stars_event_max_datetime": "2021-12-16T22:16:28.000Z", "max_issues_repo_path": "leetcode/L0750/lc763.js", "max_issues_repo_name": "brianshen1990/KeepLearning", "max_issues_repo_issues_event_min_datetime": null, "max_issues_repo_issues_event_max_datetime": null, "max_forks_repo_path": "leetcode/L0750/lc763.js", "max_forks_repo_name": "brianshen1990/KeepLearning", "max_forks_repo_forks_event_min_datetime": null, "max_forks_repo_forks_event_max_datetime": null}
{"max_stars_count": 4, "max_issues_count": null, "max_forks_count": null, "avg_line_length": 23.9705882353, "max_line_length": 230, "alphanum_fraction": 0.5865030675}
/**
763. Partition Labels

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.
 */


/**
 * @param {string} S
 * @return {number[]}
 */
var partitionLabels = function(S) {
  const cache = {};
  for ( let i = 0 ; i < S.length ; i++ ) {
      cache[S[i]] = cache[S[i]] || { beg: i, end:i };
      cache[S[i]].end = i;
  }
  
  let ret = [];
  for ( let i = 0 ; i < S.length ; ) {
      if ( cache[S[i]].beg === cache[S[i]].end ) {
          ret.push(1);
          i++;
          continue;
      } 
      // handle 
      let nextMax = cache[S[i]].end;
      // console.log("beg", i, nextMax );
      let nextIndex = i+1;
      while ( nextIndex <= nextMax && nextIndex < S.length ) {
          if ( cache[S[nextIndex]].end > nextMax ) {
              nextMax = cache[S[nextIndex]].end;
          }
          nextIndex++;
      }
      // console.log("end", i, nextMax );
      ret.push( nextMax - i + 1);
      i = nextMax + 1;
  }
  return ret;
};


/*
"ababcbacadefegdehijhklij"
"ababcbacadefegdehijhklijz"
"ababc"
"aaaa"
"abcda"
"b"
*/