How to divide letter intervals in PHP

String S consists of lowercase letters. We need to divide this string into as many segments as possible, and the same letter will only appear in one of the segments. Returns a list representing the length of each string fragment. Today we will introduce the method of dividing letter intervals.

Divide the letter interval

String S consists of lowercase letters. We need to divide this string into as many segments as possible, and the same letter will only appear in one of the segments. Returns a list representing the length of each string fragment.

Example 1:

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

Tips: The length of

S ​​is between [1, 500]. S contains only lowercase letters ‘a’ to ‘z’.

Problem-solving ideas 1

If you want to cut, you must have two pointers, the first and the last. Once the end pointer is determined, you can determine the start pointer of the next cutting. Traverse the string. If all the characters in the scanned part only appear in the scanned range, you can cut it. The scanned green characters in the picture below do not correspond to the farthest position beyond 8. If you cut at 8, the characters [0:8] will not appear elsewhere.

maintain "The farthest position that the scanned characters can go to". When scanning to this position, it will be cut. The cut characters will not appear later. Update the start pointer and prepare for the next cut.

Some variables

maxPos is a Map that records the farthest position corresponding to each letter. start is the starting position of cutting. scannedCharMaxPos The furthest position that the scanned characters can go to.

class Solution {
    /** 
    * @param String $S 
    * @return Integer[] 
    */
    function partitionLabels($S) {
        $maxPos = [];
        $length = strlen($S);
        for ($i = 0; $i < $length; $i++) { // 存放字母与它的最远位置
            $maxPos[$S[$i]] = $i;
        }
        $res = [];
        $start = 0;                        // 待切割的起始位置
        $scannedCharMaxPos = 0;            // 已扫描的字符中最远的位置
        for ($i = 0; $i < $length; $i++) {
            $curCharMaxPos = $maxPos[$S[$i]]; // 当前扫描的字符的最远位置
            $scannedCharMaxPos = max($scannedCharMaxPos, $curCharMaxPos); // 更新「已扫描的字符中最远的位置」
            if ($i == $scannedCharMaxPos) { // 正好扫描到「已扫描的字符的最远位置」，到达切割点
                $res[] = $i - $start + 1;
                $start = $i + 1;              // 更新，下一个待切割的字符串的起始位置
            }
        }
        return $res;
    }}

Recommended learning: php video tutorial

The above is the detailed content of How to divide letter intervals in PHP. For more information, please follow other related articles on the PHP Chinese website!