Strings and Characters

A std::string is an indexed sequence of characters. Competitive tasks use strings for words, codes, bracket sequences and digit representations. Basic character loops and frequency counts solve many such problems without a specialized string algorithm. This lesson counts lowercase letters, extracts a prefix, appends punctuation and compares strings lexicographically; KMP, suffix structures and other advanced methods belong in String Algorithms.

Prerequisites: Arrays and Vectors; Loops and Iteration.

Build the idea

1. 1. Decide how input is separated

   cin>>word reads one whitespace-delimited token, while getline reads an entire line including spaces. After a preceding formatted read, a leftover newline may cause getline to return an empty string; consume it deliberately when mixing styles. This program asks for one nonempty lowercase token, so ordinary extraction is sufficient and does not silently drop meaningful spaces from its contract.

2. 2. Index and inspect characters

   word[i] is the character at index i, with 0≤i<word.size(). Single quotes denote a character, as in 'a'; double quotes denote a string literal. To map lowercase English letters to indices 0..25, subtract 'a'. This mapping requires the promised alphabet and the usual contiguous lowercase encoding used by contest systems. Bytes are not the same as Unicode characters: arbitrary UTF-8 text needs different handling.

3. 3. Build a frequency array

   Initialize 26 counts to zero. For every character c, increase frequency[c−'a']. The invariant is that after a prefix has been scanned, each entry counts that letter in the scanned prefix. This proves the final counts. The example prints the count of 'a', and increases distinct only when a count first changes from zero to one.

4. 4. Transform and compare strings

   substr(0,3) copies at most the first three characters; if the remaining length is shorter, it returns the available part. word+"!" makes a concatenated string without modifying word. Comparison is lexicographic: compare the first differing character, or the shorter prefix if one ends first. Thus "ant"<"apple" is true because n comes before p, not because of length alone.

5. 5. Trace banana

   Its characters are b,a,n,a,n,a. Counts are a:3, b:1, n:2, giving three distinct letters. The first three characters form ban and concatenation yields banana!. The program also prints a fixed comparison result for ant<apple. Empty strings can exist in C++, but token input in this example is deliberately nonempty; avoid indexing the first character without checking that assumption.

This is a complete program. Compile with C++17 and enter the input described below.

// Key idea: 3. Build a frequency array Initialize 26 counts to zero.
#include<iostream>
#include<string>
int main(){
    std::string word;
    std::cin>>word;
    int frequency[26]={};
    int distinct=0;
    for(char c:word){
        int id=c-'a';
        if(frequency[id]==0){
            ++distinct;
        }
        ++frequency[id];
    }
    std::cout<<frequency[0]<<' '<<distinct<<'\n';
    std::cout<<word.substr(0,3)<<'\n'<<word+"!"<<'\n';
    std::cout<<(std::string("ant")<std::string("apple"))<<'\n';
}

Complexity analysis

O(L) time for scanning and constructing output strings, where L is word length. The fixed frequency table is O(1) auxiliary storage relative to L; the input and concatenated output occupy O(L). substring creation copies its result; general string comparison may inspect the entire shorter prefix, not always O(1).

Example input and output

One nonempty lowercase English word, length≤100000. Print count of a and number of distinct letters, its prefix of at most three letters, the word with ! appended, and the result of ant<apple.

Input

banana

Output

3 3
ban
banana!
1

The letters a,b,n occur; a occurs three times. n precedes p in the comparison ant versus apple.

Practical applications

Use direct scans for character counts, simple transformations and validation. For numbers represented as text, explicitly choose whether lexical or numeric ordering is intended. Use the String Algorithms folder when repeated pattern matching or substring queries require preprocessing beyond a basic loop.

Check your understanding

What does s.substr(2,3) request?

Put it into practice

Print the most frequent letter, breaking ties alphabetically.