Welcome to Day 5 of my 100 Days of DSA challenge! Today, I focused on solving five challenging string-based problems. These problems helped me enhance my skills in string manipulation, pattern recognition, and efficient problem-solving techniques. Tackling them was both rewarding and insightful.
Check out my GitHub repository for all the solutions and progress updates at: 100 Days of DSA
Let’s dive into the details of what I worked on today! ✨
1. Check if Two Strings are Anagrams
This code checks if two strings are anagrams. It first compares the lengths of the two strings; if they differ, they can't be anagrams. Then, it sorts both strings and compares them. If the sorted strings are identical, they are anagrams; otherwise, they are not.
Code:
#include <iostream>
#include <string>
#include <algorithm>
#include <cctype>
using namespace std;
//Function to check if two strings are anagrams
bool is_anagram(string str1, string str2) {
// If lengths are different, they cannot be anagrams
if (str1.length() != str2.length()) {
return false;
}
// Convert both strings to lowercase to make the comparison case-insensitive
transform(str1.begin(), str1.end(), str1.begin(), ::tolower);
transform(str2.begin(), str2.end(), str2.begin(), ::tolower);
// Sort both strings to compare their characters
sort(str1.begin(), str1.end());
sort(str2.begin(), str2.end());
// After sorting, if the strings are identical, they are anagrams
return str1 == str2;
}
int main() {
string str1, str2;
cout << "Enter first string: ";
getline(cin, str1);
cout << "Enter second string: ";
getline(cin, str2);
if (is_anagram(str1, str2)) {
cout << "Strings " << str1 << " and " << str2 << " are Anagrams." << endl;
}
else {
cout << "Strings " << str1 << " and " << str2 << " are not Anagrams." << endl;
}
return 0;
}
Output:
2. Find the First Non-Repeating Character in a String
This program identifies the first non-repeating character in a given string. It iterates through each character in the string and uses a nested loop to check if the character repeats elsewhere. A flag is used to track whether the current character has duplicates. If a character is found to be non-repeating, it is stored and the loop breaks.
Code:
#include <iostream>
using namespace std;
// Function to find first non-repeating character in a string
void non_repeating(string str) {
int n = str.length();
char ch = ' ';
// Loop through each character in the string
for (int i = 0; i < n; i++) {
bool flag = false; // Reset flag for each character
// Check if the current character repeats in the rest of the string
for (int j = 0; j < n; j++) {
if (i != j && str[i] == str[j]) {
flag = true; // Mark as repeating
break;
}
}
// If not repeating, it's the first non-repeating character
if (!flag) {
ch = str[i];
break;
}
}
if (ch != ' ') {
cout << "The first non-repeating character in the string is: " << ch << endl;
}
else {
cout << "There are no non-repeating characters in the string." << endl;
}
}
int main() {
string str;
cout << "Enter a string: ";
getline(cin, str);
non_repeating(str);
return 0;
}
Output:
3. Find All Substrings of a String
This program generates and prints all substrings of a given string. The function all_substrings uses two nested loops to identify the starting and ending points of each substring. The outer loop iterates through the string for the starting index, and the inner loop iterates for the ending index. For each pair of indices, the substring is extracted using str.substr() and displayed. The main function reads the input string from the user and calls the all_substrings function to perform the task.
Code:
#include <iostream>
#include <string>
using namespace std;
// Function to find all substrings of a string
void all_substrings(string str) {
int n = str.length();
cout << "All substrings of the given string are:" << endl;
// Loop to select the starting point
for (int i = 0; i < n; i++){
// Loop to select the ending point
for (int j = i; j < n; j++) {
// Extract and print the substring from i to j
cout << str.substr(i, j - i + 1) << endl;
}
}
}
int main() {
string str;
cout << "Enter a string: ";
cin >> str;
all_substrings(str);
return 0;
}
Output:
4. Replace Spaces in a String with a Special Character
This program replaces all spaces in a given string with a specified character. The replace_space function iterates through the string and checks for spaces. When a space is encountered, it is replaced with the given character. The updated string is then printed.
Code:
#include <iostream>
using namespace std;
// Function to replace spaces in the string with a specified character
void replace_space(string str, char ch) {
int n = str.length();
for (int i = 0; i < n; i++) {
if (str[i] == ' ') { // Check if the current character is a space
str[i] = ch; // Replace the space with the specified character
}
}
cout << "The replaces string is: " << str;
}
int main() {
string str;
char ch;
cout << "Enter a sentence: ";
getline(cin, str);
cout << "Enter special character to replace spaces with: ";
cin >> ch;
replace_space(str, ch);
return 0;
}
Output:
5. Find Longest Common Prefix in an Array of Strings
This program finds the longest common prefix among an array of strings. The user inputs the number of strings and the strings themselves. The function longest_common_prefix starts by assuming the first string as the prefix. It then iteratively compares the prefix with each subsequent string, character by character, to determine the shared prefix. The prefix is updated or reduced during each iteration, and if it becomes empty, the function exits early, indicating no common prefix.
Code:
#include <iostream>
#include <string>
using namespace std;
// Function to find the longest common prefix
string longest_common_prefix(string strs[], int n) {
if (n == 0) {
return ""; // Return an empty string if no input
}
string prefix = strs[0]; // Assume the first string is the prefix initially
// Compare prefix with each string in the array
for (int i = 1; i < n; i++) {
string current = strs[i];
string temp = ""; // Temporary variable to store the new prefix
// Compare characters of the prefix and current string
for (int j = 0; j < prefix.length() && j < current.length(); j++) {
if (prefix[j] == current[j]) {
temp += prefix[j]; // Add matching characters to temp
}
else {
break; // Stop when a mismatch is found
}
}
prefix = temp; // Update prefix with the new common prefix
if (prefix.empty()) { // If prefix becomes empty, no common prefix exists
break;
}
}
return prefix;
}
int main() {
int n;
cout << "Enter the number of strings: ";
cin >> n;
cin.ignore(); // Clear the buffer for getline
string strs[n];
cout << "Enter the strings:" << endl;
for (int i = 0; i < n; i++) {
getline(cin, strs[i]);
}
// Find and display the longest common prefix
string result = longest_common_prefix(strs, n);
if (result.empty()) {
cout << "There is no common prefix among the given strings." << endl;
}
else {
cout << "The longest common prefix is: " << result << endl;
}
return 0;
}
Output:
That wraps up Day 5 of my DSA challenge! Today’s string problems were both engaging and insightful, providing a deeper understanding of how to manipulate and analyze text data efficiently.
From finding substrings to handling prefixes and anagrams, these exercises reinforced essential problem-solving strategies. The longest common prefix problem stood out as a great example of refining solutions through iterative comparisons.
Excited to tackle new and more intricate challenges as I step into Day 6! 🚀