Strings: parsing, transforms, palindromesCopy Anchor Link

frequent

From Characters to StringsCopy Anchor Link

Before learning about strings, we need to know how characters are stored.

In modern computers (or rather, in our contests), we use the ASCII table to convert between characters and binary. For contests, though, you just need to master a few neat tricks.

For a digit character, we can get its corresponding integer value like this:

int(c-'0');

int(c)

We can also shift characters, for example to implement a Caesar cipher. In ASCII, 'A' is 65 and 'a' is 97, and that gap of 32 is the same for every letter pair. Wrap around the alphabet with MOD 26, otherwise the result turns into random other characters.

int(a-'a') gives a letter's position in the alphabet (0-indexed), and adding 'a' converts back.

char a;
int shift;
cin>>a>>shift;
cout<<char((int(a-'a')+shift)%26+'a');

For a negative shift, C++'s % can return a negative number, so use ((int(a-'a')+shift)%26+26)%26+'a' instead.

ord(c) gives a character's ASCII value, and chr(n) converts back.

chr((ord(a) - ord('a') + shift) % 26 + ord('a'))

Python's % returns a non-negative result when the divisor is positive, so negative shifts work with no extra handling.

What is a String?Copy Anchor Link

A string is one of the fundamental data structures in modern programming languages. It's super important, and under the hood, it's essentially a character array, which literally just means a bunch of characters strung together.

In C++, string is an STL container.

• Something like: "C++ is the best language in the world.cpp"

• Something like: "Python is the best language in the world.py"

In upcoming problems, we'll be dealing with two concepts, substrings and subsequences.

• Subsequence: the relative order of each character stays the same, and they don't have to be contiguous.
  • For example, "C++ best" is a subsequence of "C++ is the best language in the world.cpp".
• Substring: a contiguous slice of characters taken from the original string.
  • For example, "world.cpp" is a substring of "C++ is the best language in the world.cpp".

• Subsequence: the relative order of each character stays the same, and they don't have to be contiguous.
  • For example, "Python best" is a subsequence of "Python is the best language in the world.py".
• Substring: a contiguous slice of characters taken from the original string.
  • For example, "world.py" is a substring of "Python is the best language in the world.py".

We can define a string and access it via indices. Note that string indexing starts at 0.

string s;
// Similar to char s[10001];

s = "Python is the best language in the world.py"

With that, we can perform basic operations on strings: append/insert, delete, modify, search, and traverse.

In the comments below, n is the length of the string and k is the number of characters being added or removed.

s+="str";            // Append to the end, amortized O(k)
s.insert(pos,"str"); // Insert at index pos, O(n) because the tail has to shift
s.erase(pos,len);    // Erase len characters starting from index pos, O(n)
s[i]='a';            // Modify the i-th character, O(1)
for(int i=0;i<s.size();i++){ // Traverse the entire string and search, O(n)
    if(s[i]=='t'){
        cout<<i<<" ";
    }
}

s += "str"                         # append to the end
s = s[:pos] + "str" + s[pos:]      # insert at index pos
s = s[:pos] + s[pos+length:]       # erase length characters starting from index pos
s = s[:i] + "a" + s[i+1:]          # modify the i-th character (strings are immutable, so we rebuild)
for i, ch in enumerate(s):         # traverse the entire string and search
    if ch == 't':
        print(i, end=" ")

Beyond these, there are a few other commonly used methods you need to know, such as:

reverse(s.begin(),s.end()); // Reverse the entire string, O(n)
s.substr(pos,len);          // Extract a substring of len characters starting from pos, O(len), clipped at the end of the string

s[::-1]              # reverse the entire string
s[pos:pos+length]    # extract a substring of length characters starting at pos (slicing clips at the end automatically)

Well then, congrats! You've learned the most basic string operations. Next, let's dive into some more advanced algorithms.

PalindromesCopy Anchor Link

A palindrome is a special kind of string that reads the exact same forwards and backwards.

• For example: "ABCBA" is a palindrome.

In some problems, we'll run into scenarios where we need to check if a string is a palindrome.

So:

• Method 1: make a copy of the original string, reverse it, and check whether the copy and s are equal.
• Method 2: traverse the string from both ends at the same time, moving inward. If we run into mismatching characters, we mark it as false, and true otherwise.

Method 1:

string t=s;
reverse(t.begin(),t.end());
bool mark=(t==s);

Slicing can reverse a string directly, so this collapses into a one-liner:

mark = (s == s[::-1])

Method 2:

bool mark=1;
int n=s.size();
for(int i=0;i<n/2;i++){
    if(s[i]!=s[n-1-i]){
        mark=0;
        break;
    }
}

mark = True
n = len(s)
for i in range(n // 2):
    if s[i] != s[n - 1 - i]:
        mark = False
        break

Before Diving into Real ProblemsCopy Anchor Link

Input containing spaces will get cut off. For example, if the input is "Hello world!", running cin just once will only give you "Hello".

So we need to use getline to read in a whole line of data:

getline(cin, s);

This way, our result will be "Hello world!".

Pitfall: after something like cin>>n, the newline is still sitting in the input buffer, so a following getline returns an empty string. Call cin.ignore(); in between.

The three problems below only read words without spaces, so plain cin>>s is enough for them.

Some programming languages may require special handling to read a line containing spaces. However, in Python, input() reads an entire line as-is, including spaces, so no special handling is needed.

J3 Walkthrough: Secret InstructionsCopy Anchor Link

57234
00907
34100
99999

right 234
right 907
left 100

In other words:

• Except for the last line, the first two digits of each line tell us which way to turn, while the last three digits tell us the distance.
• When we read in "99999", the program terminates.

This is a simple problem.

• After reading in the data (s), grab the first two digits, add them up, and check whether the sum is zero, even, or odd.

int ch=int(s[0]-'0')+int(s[1]-'0');
if(ch==0){
    cout<<dir;
}else if(ch%2==0){
    cout<<"right ";
    dir="right ";
}else{
    cout<<"left ";
    dir="left ";
}

ch = int(s[0]) + int(s[1])
if ch != 0:
    direction = "right " if ch % 2 == 0 else "left "

• Then grab the last three digits and convert them to an integer, so that "012" prints as 12, not 012.

int d=int(s[2]-'0')*100+int(s[3]-'0')*10+int(s[4]-'0');
cout<<d<<endl;

d = int(s[2:])   # a slice plus int() also drops the leading zeros

And just like that, we can breeze through this problem:

<bits/stdc++.h> works with GCC. On MSVC or Apple clang, include <iostream>, <string>, and <algorithm> instead.

#include<bits/stdc++.h>
using namespace std;
int main(){
    string s="";
    string dir="";
    while(1){
        cin>>s;
        if(s=="99999"){
            return 0;
        }
        int ch=int(s[0]-'0')+int(s[1]-'0');
        if(ch==0){
            cout<<dir;
        }else if(ch%2==0){
            cout<<"right ";
            dir="right ";
        }else{
            cout<<"left ";
            dir="left ";
        }
        int d=int(s[2]-'0')*100+int(s[3]-'0')*10+int(s[4]-'0');
        cout<<d<<endl;
    }
}

s = input()
direction = ""
while s != "99999":
    ch = int(s[0]) + int(s[1])
    if ch != 0:
        direction = "right " if ch % 2 == 0 else "left "
    print(direction + str(int(s[2:])))
    s = input()

J3 Walkthrough: RövarspråketCopy Anchor Link

Following the processing logic, our program should look something like this:

1. Read in the data.
2. Traverse and process the string.

If the current character is a vowel (aeiou), append it directly to the ans string.

Otherwise:

First, append the consonant itself to the ans string. Then append the vowel closest to this consonant, with ties going to the earlier vowel. Finally, append the next consonant in the alphabet (skipping over vowels), where z is a special case that stays z.

First, create the two tables:

string vol="aeiou";
string con="bcdfghjklmnpqrstvwxyz";

To find the closest vowel, look for the first vowel that comes after this character (in the code below, vol[j] is that vowel).

• If we don't find one, it means the letter comes after u, so we just append u directly.
• Otherwise, compare the distance to the previous vowel vol[j-1] with the distance to the next vowel vol[j]. The previous vowel wins when it is closer or tied.

if(s[i]-vol[j-1]>vol[j]-s[i]){
    ans+=vol[j];
}else{
    ans+=vol[j-1]; // closer, or tied: take the earlier vowel
}

Next, handle the following consonant. Find the current letter's position in the consonant table and add 1 to the index. Watch out for z though: it needs a special case, which we check once, outside the search loop.

if(s[i]=='z'){
    ans+='z';
}else{
    for(int j=0;j<con.size();j++){
        if(s[i]==con[j]){
            ans+=con[j+1];
            break;
        }
    }
}

First, create the two tables:

vol = "aeiou"
con = "bcdfghjklmnpqrstvwxyz"

Python's min with a key does the whole closest-vowel search. The key (distance, vowel) sorts ties toward the earlier vowel, and letters after u automatically pick u:

closest = min(vol, key=lambda v: (abs(ord(v) - ord(ch)), v))

For the following consonant, add 1 to its index in the consonant table. z is the only special case:

nxt = "z" if ch == "z" else con[con.index(ch) + 1]

3. Finally, output the answer ans.

And that solves the problem! Solution:

#include<bits/stdc++.h>
using namespace std;
string vol="aeiou";
string con="bcdfghjklmnpqrstvwxyz";
int main(){
    string s;
    cin>>s;
    string ans="";
    for(int i=0;i<s.size();i++){
        bool flg=0;
        for(int j=0;j<=4;j++){
            if(s[i]==vol[j]){
                ans+=s[i];
                flg=1;
                break;
            }
        }
        if(flg){
            continue;
        }
        ans+=s[i];
        flg=0;
        for(int j=0;j<=4;j++){
            if(vol[j]>s[i]){
                flg=1;
                if(s[i]-vol[j-1]>vol[j]-s[i]){
                    ans+=vol[j];
                }else{
                    ans+=vol[j-1];
                }
                break;
            }
        }
        if(!flg){
            ans+='u';
        }
        if(s[i]=='z'){
            ans+='z';
        }else{
            for(int j=0;j<con.size();j++){
                if(s[i]==con[j]){
                    ans+=con[j+1];
                    break;
                }
            }
        }
    }
    cout<<ans;
}

vol = "aeiou"
con = "bcdfghjklmnpqrstvwxyz"

s = input()
ans = ""
for ch in s:
    ans += ch
    if ch in vol:
        continue
    ans += min(vol, key=lambda v: (abs(ord(v) - ord(ch)), v))
    ans += "z" if ch == "z" else con[con.index(ch) + 1]

print(ans)

J3 Walkthrough: Cold CompressCopy Anchor Link

This is a good warm-up, and it introduces a pattern you'll reuse often: scan a string while tracking the current run.

4
+++===!!!!
777777......TTTTTTTTTTTT
(AABBC)
3.1415555

3 + 3 = 4 !
6 7 6 . 12 T
1 ( 2 A 2 B 1 C 1 )
1 3 1 . 1 1 1 4 1 1 4 5

We need to implement RLE (run-length encoding), so the idea goes like this:

• Traverse the entire string, and while we're at it, set up some initial values. Starting directly from the second character makes things much more convenient.

int cnt=1;
char c=s[0];

cnt = 1
c = s[0]

• cnt is the count of occurrences, and c is the current character.
• While traversing the string:
  • If this character is the same as c, do cnt++.
  • Otherwise, output cnt and c, and update cnt and c to the current state.
• At the very end, output cnt and c one more time so we don't miss the last segment.

Well done! That's another J3 down.

Solution:

#include<bits/stdc++.h>
using namespace std;
int main(){
    int nt;
    cin>>nt;
    for(int t=1;t<=nt;t++){
        string s;
        cin>>s;
        int cnt=1;
        char c=s[0];
        for(int i=1;i<s.size();i++){
            if(s[i]!=c){
                cout<<cnt<<" "<<c<<" ";
                cnt=1;
                c=s[i];
            }else{
                cnt++;
            }
        }
        cout<<cnt<<" "<<c<<endl;
    }
}

for _ in range(int(input())):
    s = input()
    cnt = 1
    c = s[0]
    for i in range(1, len(s)):
        if s[i] != c:
            print(cnt, c, end=' ')
            cnt = 1
            c = s[i]
        else:
            cnt += 1
    print(cnt, c)

Partial content translated by Gemini-4-Argon from Chinese.