Introduction (covers string introduction, vowels/consonants, character search, character frequency, first non-repeating character, reverse string, remove spaces, toggle case)

Given a string, the task is to understand how to visit each character of the string one by one and perform basic operations on it.

A string is a sequence of characters. These characters can be letters, digits, spaces, or symbols.

Example 1

Input:

s = "take"

Output:

Vowels = 2
Consonants = 2

Explanation:

The vowels are a and e.

The consonants are t and k.

So, the string has 2 vowels and 2 consonants.

Example 2

Input:

s = "Take U Forward"

Output:

String after removing spaces = "TakeUForward"

Explanation:

The original string contains spaces between words.

When we traverse the string, we copy only non-space characters.

So, the final string becomes "TakeUForward".

Approach : Basic Character-by-Character Traversal

Think of a teacher checking answer sheets in a classroom.
The teacher does not check all answer sheets together. The teacher picks the first answer sheet, checks it, then moves to the next one, and continues this until every answer sheet is checked.

String traversal works in the same way.
We start from the first character. We check what the character is. Then we decide what to do with it.

If the character is a vowel, increase vowel count.
If the character is a consonant, increase consonant count.
If the character is equal to the target character, increase frequency.
If the character is a space, skip it while removing spaces.
If the character is lowercase, convert it to uppercase while toggling case.

This works because most basic string problems depend on checking each character once.

The important decision is:
What should we do with the current character?
Once we know this, traversal becomes easy.

Algorithm

Start from the first character of the string.
This is needed because traversal should begin from the left side.
If we remove this step, we will not know where to start checking.
Visit each character one by one.
This is the main part of traversal.
If we skip characters, the answer may become wrong because every character can affect the final result.
For each character, check what operation is required.
For example, we may need to count vowels, search a character, remove spaces, or toggle case.
If we do not check the operation properly, we may update the wrong answer.
If the task is to count vowels and consonants, check whether the character is an alphabet first.
This is needed because spaces, digits, and symbols should not be counted as consonants.
If we remove this check, characters like '1', '@', or space may be counted incorrectly.
If the task is character search, compare the current character with the target character.
If both are equal, we found the character.
If we remove this comparison, we cannot know whether the target exists or not.
If the task is character frequency, increase the count whenever the current character matches the target.
This is needed because frequency means the number of times a character appears.
If we remove this update, the count will always remain wrong.
If the task is first non-repeating character, first count all character frequencies, then traverse again to find the first character with frequency 1.
This is needed because we cannot know if a character is repeating until we know its total count.
If we remove the second traversal, we may not return the first non-repeating character in the original order.
If the task is reverse string, read characters from the end and build the answer.
This is needed because reversing means the last character should come first.
If we traverse normally from left to right, the string will not be reversed.
If the task is remove spaces, copy only characters that are not spaces.
This is needed because spaces should not be part of the final answer.
If we copy every character, spaces will remain.
If the task is toggle case, change lowercase letters to uppercase and uppercase letters to lowercase.This is needed because toggle case means changing the case of alphabet characters.If we do not check lowercase and uppercase separately, the conversion may become wrong.

Dry Run

Diagram 1

Solution

1// C++ program to implement Introduction to Basic Traversal in Strings
2#include <bits/stdc++.h>
3using namespace std;
4
5class Solution {
6public:
  // Checks whether a character is a vowel.
  // Uppercase vowels are also handled by converting the character to lowercase.
  bool isVowel(char ch) {
      ch = tolower(ch);
11
      return ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u';
  }
14
  // Counts vowels and consonants in the string.
  // Only alphabet characters are considered because spaces, digits, and symbols
  // are neither vowels nor consonants.
  pair<int, int> countVowelsAndConsonants(string s) {
      int vowels = 0;
      int consonants = 0;
21
      for (char ch : s) {
          // This check prevents spaces, digits, and symbols from being counted as consonants.
          if (isalpha(ch)) {
              if (isVowel(ch)) {
                  vowels++;
              } else {
                  consonants++;
              }
          }
      }
32
      return {vowels, consonants};
  }
35
  // Searches for the first occurrence of the target character.
  // Returns the index if found, otherwise returns -1.
  int searchCharacter(string s, char target) {
      for (int i = 0; i < s.length(); i++) {
          // Return immediately because the first matching index is required.
          if (s[i] == target) {
              return i;
          }
      }
45
      // -1 is used because it cannot be a valid string index.
      return -1;
  }
49
  // Counts how many times the target character appears in the string.
  // This comparison is case-sensitive, so 'A' and 'a' are treated differently.
  int characterFrequency(string s, char target) {
      int count = 0;
54
      for (char ch : s) {
          if (ch == target) {
              count++;
          }
      }
60
      return count;
  }
63
  // Finds the first character that appears only once in the string.
  // It uses frequency counting first, then checks the string again to preserve order.
  char firstNonRepeatingCharacter(string s) {
      // Size 256 is used to cover standard ASCII characters.
      vector<int> freq(256, 0);
69
      for (char ch : s) {
          freq[ch]++;
      }
73
      // Second traversal is needed because the answer depends on original string order.
      for (char ch : s) {
          if (freq[ch] == 1) {
              return ch;
          }
      }
80
      // '\0' represents that no non-repeating character exists.
      return '\0';
  }
84
  // Reverses the given string by reading characters from the end.
  string reverseString(string s) {
      string result = "";
88
      // The last character becomes the first character in the reversed string.
      for (int i = s.length() - 1; i >= 0; i--) {
          result += s[i];
      }
93
      return result;
  }
96
  // Removes all normal spaces from the string.
  string removeSpaces(string s) {
      string result = "";
100
      for (char ch : s) {
          // Only non-space characters are copied into the result.
          if (ch != ' ') {
              result += ch;
          }
      }
107
      return result;
  }
110
  // Toggles the case of alphabet characters.
  // Lowercase becomes uppercase, uppercase becomes lowercase,
  // and digits, spaces, and symbols remain unchanged.
  string toggleCase(string s) {
      string result = "";
116
      for (char ch : s) {
          if (islower(ch)) {
              result += toupper(ch);
          } else if (isupper(ch)) {

Time Complexity: O(N)

Here, N is the length of the string.

In basic traversal, we check each character one by one. So, if the string has N characters, the loop runs N times.

Most operations like counting vowels, searching a character, removing spaces, reversing, and toggling case take:

O(N)

For first non-repeating character, we may traverse the string twice. But O(N) + O(N) is still treated as:

O(N)

Space Complexity: O(1) or O(N)

For counting vowels, searching a character, or counting frequency of one character, we use only a few variables.

So, space complexity is:

O(1)

For reversing a string, removing spaces, or toggling case, we create a new string to store the answer.

So, space complexity is:

O(N)

For first non-repeating character, space is O(1) with a fixed-size array and O(N) with a hashmap.

FAQs about Introduction to Basic Traversal in Strings

1. What is string traversal?

String traversal means visiting every character of a string one by one.

2. Why is string traversal important?

Many beginner string problems are solved by checking each character carefully. That is why traversal is the base of string problem solving.

3. Can every string problem be solved using one traversal?

No. Some problems can be solved in one traversal, but some need two traversals or extra storage.

4. Why do we check whether a character is an alphabet before counting consonants?

Because only alphabet letters can be vowels or consonants. Spaces, digits, and symbols should not be counted as consonants.

5. Why does first non-repeating character need frequency counting?

Because we need to know how many times each character appears before deciding whether it is repeating or not.

6. Is reversing a string also traversal?

Yes. Reversing a string is also traversal, but we start from the last character and move toward the first character.

7. What is the safest way to remove spaces?

Create a new string and copy only characters that are not spaces.

8. What happens during toggle case?

Lowercase letters become uppercase, uppercase letters become lowercase, and other characters remain unchanged.