解题思路

这是一个字符串构造问题，要求构造的新字符串t在每个位置上都和原字符串s不同，但使用的字符集必须相同。
解题思路如下：

  1. 首先获取原字符串s的字符集（去重后的所有字符）
  2. 如果字符集大小为1，则无法构造（因为每个位置都必须不同）
  3. 对于字符集大小≥2的情况，把当前字符变为字符集内位置的下一位

代码

#include <iostream>
#include <string>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	string s;
	cin>>s;
	set<char> chk(s.begin(),s.end());
	vector<char> v(chk.begin(),chk.end());
	int m=v.size(),w;
	if(m==1)
	{
		cout<<"-1";
		return 0;
	}
	for(char &c:s)
	{
		w=find(v.begin(),v.end(),c)-v.begin();
		cout<<v[(w+1)%m];
	}
	return 0;
}

import java.util.*;
public class ZT6 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s=sc.next();
        int n=s.length(),m,i,w;
        Set<Character> chk=new HashSet();
        for(i=0;i<n;++i)
            chk.add(s.charAt(i));
        ArrayList<Character> v=new ArrayList(chk);
        m=v.size();
        if(m==1)
            System.out.println(-1);
        else{
            for(i=0;i<n;++i){
                w=v.indexOf(s.charAt(i));
                System.out.print(v.get((w+1)%m));
            }
        }
    }
}


s=input()
v=list(set(s))
m=len(v)
if(m==1):
    print(-1)
else:
    for i in s:
        w=v.index(i)
        print(v[(w+1)%m],end='')

算法及复杂度

  • 算法：构造法。使用字符集中的字符交替构造新字符串。
  • 时间复杂度： ，其中n为字符串长度。
  • 空间复杂度： ，其中k为字符集大小，一般不超过26。