想要精通算法和SQL的成长之路 - 划分字母区间

• 前言
• 一. 划分字母区间
• • 1.1 记录每个字母出现的最远位：
  • 1.2 分割区间

前言

想要精通算法和SQL的成长之路 - 系列导航

一. 划分字母区间

原题链接

字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。

示例：

• 输入：S = “ababcbacadefegdehijhklij”
• 输出：[9,7,8]
• 解释：划分结果为 “ababcbaca”, “defegde”, “hijhklij”。每个字母最多出现在一个片段中。像 “ababcbacadefegde”, “hijhklij” 的划分是错误的，因为划分的片段数较少。

看到这个题目，我先观察了一下示例的返回。试想一下，是根据什么来进行划分的？

如果下一个元素和当前元素不一致，就划分一个，那么结果就应该是： [“a”,“b”…]。那么肯定是不对的。

那么如果是下一个元素（i+1）以及下下个元素（i+2），都和当前元素不一致，就划分一个。貌似也不对：那么前几个应该是：[“aba”,“bcb”,“aca”…]。

• 遍历到a（下标为2）的时候，发现后面的b和c都不一致。
• 遍历到b（下标为3）的时候，发现后面的a和c都不一致。

到这里就能发现，从这个角度来思考肯定是走不通的，那么我们可以这么想：

• 遍历字符串的时候，记录每个字符串它目前出现过的最远位置。
• 当你遍历到某个字符串的时候，发现当前位置就是之前遍历过的所有字母的最远边界，那么当前位置就是分割点。

1.1 记录每个字母出现的最远位：

首先：

• 字符串的长度在[1, 500]之间。
• 字符串只包含小写字母 ‘a’ 到 ‘z’ 。

那么我们可以用一个固定大小的数组，统计a-z中的所有字母，它在字符串中最后出现的位置是哪里。

int[] lastIndex = new int[27];
for (int i = 0; i < s.length(); i++) {lastIndex[s.charAt(i) - 'a'] = i;
}

1.2 分割区间

遍历过程中，我们如何确定当前分割区间的右边界？

1. 维护当前分割区间的最远右边界值curMaxRight。
2. 一旦当前的遍历下标 i 和 curMaxRight 相等，就说明到达分割边界。
3. 因为我们要计算区间长度，因此光有一个右边界还不够，还需要一个左边界left。找到分割边界的时候，左边界就好处理了，下一个左边界就是curMaxRight+1。

// 记录左边界和右边界
int left = 0, curMaxRight = 0;
for (int i = 0; i < s.length(); i++) {// 当前这个字符对应的最原位置int lastIndex = lastIndexArr[s.charAt(i) - 'a'];// 遍历的同时，还要更新当前区间中重复出现的最远位置。curMaxRight = Math.max(curMaxRight, lastIndex);// 如果两者相等，说明当前位置就是边界值if (curMaxRight == i) {// 计入结果,计算当前区间的大小res.add(curMaxRight - left + 1);// 更新左边界left = i + 1;}
}

那么最终结果如下：

public List partitionLabels(String s) {ArrayList res = new ArrayList<>();int[] lastIndexArr = new int[27];for (int i = 0; i < s.length(); i++) {lastIndexArr[s.charAt(i) - 'a'] = i;}// 记录左边界和右边界int left = 0, curMaxRight = 0;for (int i = 0; i < s.length(); i++) {// 当前这个字符对应的最原位置int lastIndex = lastIndexArr[s.charAt(i) - 'a'];// 遍历的同时，还要更新当前区间中重复出现的最远位置。curMaxRight = Math.max(curMaxRight, lastIndex);// 如果两者相等，说明当前位置就是边界值if (curMaxRight == i) {// 计入结果,计算当前区间的大小res.add(curMaxRight - left + 1);// 更新左边界left = i + 1;}}return res;
}