蓝桥杯-稍大的字符串

• 题目

  标题：稍大的串

  串可以按照字典序进行比较。例如：
  abcd 小于 abdc

  如果给定一个串，打乱组成它的字母，重新排列，可以得到许多不同的串，在这些不同的串中，有一个串刚好给定的串稍微大一些。科学地说：它是大于已知串的所有串中最小的串。你的任务就是求出这个“稍大的串”。

  例如：
  输入串：
  abfxy
  程序应该输出：
  abfyx

  再例如：
  输入串：
  ayyyxxff
  程序应该输出：
  fafxxyyy

  数据规模约定：
  输入的串不超过1000个字符。

  特例：
  如果已知的串已经是所有重组串中最大的，则原样输出读入的那个串。

• 思路

  假定输入字符串长度为L，我们倒序遍历字符串，直到第一次找到一个位置x[i] < x[i+1]，记子串[0,i]为新串S1，然后反转子串[i+1,L]得到一个新串S2，接着将下x[i]插入到S2的第2个位置。最后拼接字符串S1和S2。

• 代码

Java版本

import java.util.Scanner;

public class BiggerString {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        int i = 0;
        int len = s.length();
        for(i=len-1;i>0;i--) {
            if(s.charAt(i)>s.charAt(i-1))
                break;
        }
        if(i==0) {
            System.out.println(s);
        } else {
            //取出最后的降序部分，反转
            StringBuilder sb = new StringBuilder(s.substring(i, len));
            sb = sb.reverse();
            //插入目标字符
            sb.insert(1, s.charAt(i-1));
            //插入在目标字符之前的字符串
            sb.insert(0, s.substring(0, i-1));
            System.out.println(sb.toString());
        }
    }
}

Python版本

#稍大的串
s = raw_input()
i = len(s)-1
while i>0:
    if(s[i]>s[i-1]):
        break
    i -= 1
#i-1
if i!=0:
    l = list(s)
    l = l[:i-1] + l[:i-1:-1]
    l.insert(i,s[i-1]) 
    s = ''.join(l)
print s

• 结果

azyxtsr
rastxyz