【Lintcode】962. Condition String

题目地址：

https://www.lintcode.com/problem/condition-string/description

给定一个只含a - f的字符串$s$，其长度为$n$，要求对其进行删除，使得：
1、所有的a在c和e之前且所有的c在e之前；
2、所有的b在d和f之前且所有的d在f之前。
返回所能得到的字符串的最大长度。

其实就是算只含ace的最长上升子序列和只含bdf的最长上升子序列的长度。这里的上升都是指非严格上升。而算最长上升子序列的长度，可以用偏序集的分解定理来做。关于偏序集分解定理，可以参考https://blog.csdn.net/qq_46105170/article/details/108616895。代码如下：

import java.util.Arrays;
import java.util.List;

public class Solution {
    /**
     * @param s: a string only contains `a-f`
     * @return: The longest length that satisfies the condition
     */
    public int conditionString(String s) {
        // write your code here
        return LIS(s, new char[s.length()], Arrays.asList('a', 'c', 'e')) 
        	+ LIS(s, new char[s.length()], Arrays.asList('b', 'd', 'f'));
    }
    
    private int LIS(String s, char[] f, List<Character> chars) {
        int idx = 0;
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (!chars.contains(ch)) {
                continue;
            }
        
        	// 得到f[0 : r]中第一个大于target的位置。注意，这里f是单调上升的
            int pos = binarySearch(f, idx - 1, ch);
            // 如果没找到，则开一个新反链；否则将ch加到pos所在反链后面去
            if (pos == -1) {
                f[idx++] = ch;
            } else {
                f[pos] = ch;
            }
        }
        
        return idx;
    }
    
    // 在f[0 : r]的范围内二分出第一个大于target的位置
    private int binarySearch(char[] f, int r, char target) {
        int l = 0;
        if (l > r) {
            return -1;
        }
        
        while (l < r) {
            int m = l + (r - l >> 1);
            if (f[m] > target) {
                r = m;
            } else {
                l = m + 1;
            }
        }
        
        return f[l] > target ? l : -1;
    }
}

时间复杂度$O(n\log n)$，空间$O(n)$。

本文地址：https://blog.csdn.net/qq_46105170/article/details/109635371