/**
 * 给定长度为N的字符串S(只包含大写英文字母)，要构造一个长度为N的字符串T。
 * 起初，T是一个空字符串，随后反复进行下列任意操作
 * 1.从S的头部删除一个字符，加到T的尾部
 * 2.从S的尾部删除一个字符，加到T的尾部
 * 目标是要构造字典序尽可能小的字符串T
 * 字典序是指从前到后比较两个字符串大小的方法。首先比较第1个字符，如果不同则第一个字符小的字符串更小，
 * 如果相同则继续比较第2个字符...如此继续来比较整个字符串的大小.
 * @author haofan.whf
 * @version $Id: BestCowLine.java, v 0.1 2018年06月12日 下午6:42 haofan.whf Exp $
 */
public class BestCowLine {

    /**
     * 思路，贪心算法
     * 要组成最小字典序的字符串我们只需要不断的将S.charAt(0)和S.charAt(S.length-1)中
     * 较小的那个添加到结果字符串的尾部即可
     * 唯一的问题是当S.charAt(0)==S.charAt(S.length-1)
     * 我们还需要继续比较S.charAt(1)和S.charAt(S.length-2)...直到分出大小为止
     * 那么由特殊到一般，我们要做的就是比较
     * S.charAt(0 + i)==S.charAt(S.length - 1 - i)的大小
     * if(S.charAt(0 + i) < S.charAt(S.length - 1 - i)){
     *     将S头部的字符放入结果尾部
     * }else{
     *     将S尾部的字符放入结果尾部
     * }
     * @param N
     * @param S
     */
    public void solution(int N, String S){
        StringBuilder tsb = new StringBuilder();
        int start = 0;
        int end = N - 1;
        while (start <= end){
            boolean left = false;
            for (int i = 0; start + i <= end; i++) {
                if(S.charAt(start + i) < S.charAt(end - i)){
                    left = true;
                    break;
                }else if(S.charAt(start + i) > S.charAt(end - i)){
                    left = false;
                    break;
                }
            }
            if(left){
                tsb.append(S.charAt(start ++));
            }else{
                tsb.append(S.charAt(end --));
            }
        }
        System.out.println(tsb);
    }
}