Codeforces Problem 708A Letters Cyclic Shift

Accept: 0 Submit: 0
Time Limit: 1 second Memory Limit : 256 megabytes

Problem Description

You are given a non-empty string s consisting of lowercase English letters. You have to pick exactly one non-empty substring of s and shift all its letters 'z' 'y' 'x' 'b' 'a' 'z'. In other words, each character is replaced with the previous character of English alphabet and 'a' is replaced with 'z'.

What is the lexicographically minimum string that can be obtained from s by performing this shift exactly once?

Input

The only line of the input contains the string s (1?≤?|s|?≤?100?000) consisting of lowercase English letters.

Output

Print the lexicographically minimum string that can be obtained from s by shifting letters of exactly one non-empty substring.

Sample Input

   codeforces 
   
 abacaba

Sample Output

   bncdenqbdr 
   
 aaacaba

Hint

String s is lexicographically smaller than some other string t of the same length if there exists some 1?≤?i?≤?|s|, such that s1?=?t1,?s2?=?t2,?...,?si?-?1?=?ti?-?1, and si?<?ti.

Problem Idea

解题思路:

【题意】
从仅有小写字母组成的字符串s中挑选出一个非空子串

将该子串中的每个字母均替换成前一个字母,如'b'换成'a','c'换成'b',以此类推,特别的,'a'要换成'z'

问经过一次转换之后,字典序最小的字符串s为多少

【类型】
implementation

【分析】

首先,何为字典序最小,大家应该都理解

然后,题目的替换操作,很明显会将字符串s的字典序变小,但是唯一一个特例是字母'a',它替换之后反而会使得字典序变小

于是乎,字母'a'成了突破口,凡是遇到字母'a',能不替换就不替换

也就意味着,我们要替换除'a'之外的其他字母

上述这种,能够替换的有两部分,红色虚线及绿色虚线,从字典序大小考虑出发,越靠前的字母变小,整体字典序越小

所以,我们会替换红色虚线处的字母,而不是绿色虚线处的字母

当然,此题最值得注意的是"exactly one non-empty substring"

这就意味着全'a'串也要变,即字符串"aaaaaaa",我们要替换其中的字母(会使得字典序比原来大),但又要使字典序最小,所以只能将最后一个'a'->'z'

【时间复杂度&&优化】
O(n)

题目链接→Codeforces Problem 708A Letters Cyclic Shift

Source Code

/*Sherlock and Watson and Adler*/
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<queue>
#include<stack>
#include<math.h>
#include<vector>
#include<map>
#include<set>
#include<bitset>
#include<cmath>
#include<complex>
#include<string>
#include<algorithm>
#include<iostream>
#define eps 1e-9
#define LL long long
#define PI acos(-1.0)
#define bitnum(a) __builtin_popcount(a)
using namespace std;
const int N = 100005;
const int M = 100005;
const int inf = 1000000007;
const int mod = 1000000007;
char s[N];
int main()
{int i,k=0;bool flag=true;scanf("%s",s);for(i=0;s[i]!='\0';i++)if(s[i]!='a')break;for(;s[i]!='\0';i++){if(s[i]=='a')break;s[i]--;k++;}if(!k)s[strlen(s)-1]='z';puts(s);return 0;
}

菜鸟成长记

Codeforces Problem 708A Letters Cyclic Shift(implementation)