Table of contents
- Q1. Write a program to check if two strings are anagrams.
- Q2. Solve the problem of finding the first non-repeating character in a string.
- Q3. Write a function to find all substrings of a string.
- Q4. Implement a program to replace spaces in a string with a special character (e.g., %20).
- Q5. Solve the "longest common prefix" problem for an array of strings.
Today’s practice was all about diving deeper into string manipulation with more advanced problems. I worked on a variety of challenges that ranged from checking if two strings are anagrams, to identifying the first non-repeating character in a string. I also tackled problems like finding all substrings of a string, replacing spaces with a special character (like %20), and solving the "longest common prefix" problem for an array of strings. Each exercise helped me understand different aspects of string operations, providing a solid foundation for more complex algorithms.
Check out my progress in my GitHub repository: github.com/AayJayTee/100-Days-DSA.
Q1. Write a program to check if two strings are anagrams.
#include <iostream>
using namespace std;
void check_anagram(string str1, string str2){
int n1 = str1.size(), n2 = str2.size();
int freq1[26] = {0}, freq2[26] = {0}; // Frequency arrays for both strings
if (n1 != n2) { // Check if lengths are the same
cout << "Strings cannot be anagrams due to diff. sizes";
}
else {
for (int i = 0; i < n1; i++) {
freq1[str1[i] - 'a']++; // Update frequency for first string
freq2[str2[i] - 'a']++; // Update frequency for second string
}
for (int k = 0; k < 26; k++) {
if (freq1[k] != freq2[k]) { // Compare frequencies of characters
cout << "They are not anagrams";
return;
}
}
}
cout << "They are anagrams"; // Output if they are anagrams
}
int main()
{
string str1, str2;
cout << "Enter first string: ";
getline(cin, str1);
cout << "Enter second string: ";
getline(cin, str2);
check_anagram(str1, str2);
return 0;
}
This program checks if two strings are anagrams by comparing the frequency of each character. It first ensures the strings have the same length, as strings of different lengths can't be anagrams. Then, it counts the occurrences of each character in both strings using frequency arrays. If any character’s frequency doesn't match between the two strings, they are not anagrams. If all frequencies match, the strings are confirmed as anagrams. This solution works efficiently in O(n) time complexity, where n is the length of the string.
Q2. Solve the problem of finding the first non-repeating character in a string.
#include <iostream>
using namespace std;
#include <cctype>
void first_non_repeating(string str){
for(int i=0;i<str.size();i++){ //looping through each character in string
int count=0; //count to maintain frequency of each character
for(int j=0;j<str.size();j++){ //looping in order to compare the characters
if(tolower(str[i])==tolower(str[j])){ //comparsion after conversion to lowercase
count+=1;
}
}
if(count==1){ //character having frequency of 1
cout<<"First non repeating character is: "<<str[i];
break; //breaking the loop in order to obtain only first non repeating character
}
}
}
int main()
{
string str;
cout<<"Enter string: ";
getline(cin,str);
first_non_repeating(str);
return 0;
}
This program finds the first non-repeating character in a string. It loops through each character in the string and, for each character, counts its occurrences by comparing it with every other character in the string. The comparison is case-insensitive, achieved by converting both characters to lowercase using tolower(). If a character appears only once (i.e., count == 1), it is identified as the first non-repeating character, and the loop breaks to return the result. The program stops as soon as the first non-repeating character is found, ensuring efficiency in terms of early termination.
Q3. Write a function to find all substrings of a string.
#include <iostream>
using namespace std;
void find_all_substrings(string str){
for(int i=0;i<str.size();i++){ //looping through all characters(start index)
for(int j=i;j<str.size();j++){ //looping through all characters(end index)
cout<<str.substr(i,j-i+1)<<endl; //printing substrings from i to j
}
}
}
int main()
{
string str;
cout<<"Enter string: ";
getline(cin,str);
find_all_substrings(str);
return 0;
}
This program generates and prints all possible substrings of a given string. It uses two nested loops to cover all possible starting (i) and ending (j) indices of substrings. The outer loop sets the starting index i, while the inner loop sets the ending index j. The function substr(i, j-i+1) extracts the substring starting from index i and ending at index j. Each substring is printed in a new line. The outer loop runs for each character in the string, and the inner loop runs from the starting index to the end of the string, ensuring all possible substrings are covered.
Q4. Implement a program to replace spaces in a string with a special character (e.g., %20).
#include <iostream>
using namespace std;
void replace_space(string str,string a){
for(int i=0;i<str.size();i++){ // Iterating through the string
if (str[i]==' '){ // Condition to chek spaces
str.replace(i,1,a); // Replacing spaces with special character
}
}
cout<<"String after replacing spaces is: "<<str;
}
int main()
{
string str;
cout<<"Enter string: ";
getline(cin,str);
string a;
cout<<"Enter replacing character: ";
getline(cin,a);
replace_space(str,a);
return 0;
}
This program takes a string and replaces all spaces in it with a specified character or string. The replace_space function iterates through each character of the input string and checks if the current character is a space. If it finds a space, it uses the replace function to replace that space with the provided string. After processing the entire string, the modified version is displayed. The main function first prompts the user to input the string and the replacement string, then it calls the replace_space function to perform the replacement. This approach helps in manipulating strings to replace spaces with custom characters efficiently.
Q5. Solve the "longest common prefix" problem for an array of strings.
#include <iostream>
using namespace std;
void common_prefix(string arr[],int n){
string prefix = arr[0];
for(int i=1;i<n;i++){ //loop to iterate through strings in tha array
for(int j=0;j<prefix.size();j++){ //loop to iterate through characters of prefix and string of the array
if(prefix[j]!=arr[i][j]){
prefix=prefix.substr(0,j); //changing prefix at the point where adjacent strings have different characters
}
}
}
cout<<"Longest common prefix is: "<<prefix;
}
int main()
{
string arr[4]={"interstellar", "internet", "interval", "interact"};
int n= sizeof(arr)/sizeof(arr[0]);
common_prefix(arr,n);
return 0;
}
This program solves the "longest common prefix" problem for an array of strings. The common_prefix function starts by assuming the first string in the array as the initial prefix. It then iterates through the other strings in the array, comparing each character of the current prefix with the corresponding character of the current string. If a mismatch is found, it updates the prefix by truncating it up to the last matching character. This process continues for all strings in the array. After processing all strings, the longest common prefix is displayed. The main function initializes the array of strings and calls the common_prefix function to compute and display the result.
Today's practice allowed me to enhance my understanding of advanced string operations. Whether it was comparing anagrams, identifying unique characters, or manipulating substrings, each problem added a valuable layer to my string manipulation toolkit. I’m excited to continue improving my skills in this area and tackle even more advanced string challenges. Onward to Day 6!