Lintcode 1379. The Longest Scene

A string, each character representing a scene. Between two identical characters is considered to be a continuous scene. For example: abcda, you can think of these five characters as the same scene. Or acafghbeb can think of two aca and beb scenes. If there is a coincidence between the scenes, then the scenes are combined. For example, abcab, where abca and bcab are coincident, then the five characters are considered to be the same scene. Give a string to find the longest scene.

Example

Example 1

Input: "abcda"
Output: 5
Explanation:
The longest scene is "abcda".

Example 2

Input: "abcab"
Output: 5
Explanation:
The longest scene is "abcab".

Notice

• 1 <= |str| <=1e5
• str contains only lowercase letters

Solution:

First of all, for each character, we note down the position of the rightmost same character it can reach. E.g. abcdad. For character a, the position of the rightmost is 4. 

After that, we can form a list of intervals with start and end position of each character. Then the problem is to merge the intervals. 

Code (Java):

 

public class Solution {
    /**
     * @param str: The scene string
     * @return: Return the length longest scene
     */
    public int getLongestScene(String str) {
        // Write your code here
        if (str == null || str.length() == 0) {
            return 0;
        }
        
        if (str.length() == 1) {
            return 1;
        }
        
        // pos saves the rightmost position of each character
        int[] pos = new int[26];
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            pos[c - 'a'] = i;
        }
        
        // store the intervals into the list. Note that it's already sorted by the start time
        List<Interval> intervals = new ArrayList<>();
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            if (pos[c - 'a'] != i) {
                intervals.add(new Interval(i, pos[c - 'a']));
            }
        }
        
        // now it's time to merge and get the longest interval
        Interval prev = null;
        int ans = 1;
        
        for (int i = 0; i < intervals.size(); i++) {
            Interval curr = intervals.get(i);
            if (prev == null || prev.end < curr.start) {
                prev = curr;
            } else { // overlap
                prev.start = Math.min(prev.start, curr.start);
                prev.end = Math.max(prev.end, curr.end);
            }
            
            if (prev.end - prev.start + 1 > ans) {
                ans = prev.end - prev.start + 1;
            }
        }
        
        if (prev != null) {
            ans = Math.max(ans, prev.end - prev.start + 1);
        }
        
        return ans;
        
    }
}

class Interval {
    int start;
    int end;
    
    public Interval(int start, int end) {
        this.start = start;
        this.end = end;
    }
}