Strings are a sequence of characters, and are one of the most fundamental data structures in Competitive Programming. String problems are very common in competitive programming contests, and can range from simple to very challenging. In this article we are going to discuss about most frequent string tips and tricks that will help a programmer during Competitive Programming.
string str = "Learn Competitive Programming with GFG!";
cout << "Substring from index 6 to 16 = "
<< str.substr(6, 11) << "\n";
return0;
}
Java
importjava.io.*;
classGFG {
publicstaticvoidmain(String[] args)
{
String str
= "Learn Competitive Programming with GFG!";
System.out.println("Substring from index 6to 16= "
+ str.substring(6, 17));
}
}
Python3
Str="Learn Competitive Programming with GFG!"
print(f"Substring fromindex 6to 16={Str[6:17]}")
Output
Substring from index 6 to 16 = Competitive
Competitive Programming Tips for Strings in C++:
1. Pass by reference:
We should always pass the reference of strings to avoid making copies of the original string which is quite inefficient.
C++
#include <iostream>
usingnamespacestd;
// Pass by value
intcountSpaceSlow(string str, intidx)
{
if(idx == str.length())
return0;
returncountSpaceSlow(str, idx + 1)
+ (str[idx] == ' '? 1 : 0);
}
// Pass by reference
intcountSpaceFast(string& str, intidx)
{
if(idx == str.length())
return0;
returncountSpaceSlow(str, idx + 1)
+ (str[idx] == ' '? 1 : 0);
}
intmain()
{
string str = "Learn Competitive programming with GFG!";
cout << countSpaceSlow(str, 0) << "\n";
cout << countSpaceFast(str, 0) << "\n";
return0;
}
Output
4
4
2. push_back() vs + operator:
We should always use push_back() function instead of + operator, to add a character at the end of the string. This is because the time complexity of + operator depends on the length of the string O(N) whereas push_back() simply pushes the character at the end in O(1) time complexity. So, if we need to append characters in a loop, push_back() will have much better performance as compared to + operator.
C++
#include <iostream>
usingnamespacestd;
// Slow because of + operator
string filterLowerCaseSlow(string str)
{
string res = "";
for(inti = 0; i < str.length(); i++) {
if(str[i] >= 'a'&& str[i] <= 'z')
res += str[i];
}
returnres;
}
// Fast because of push_back()
string filterLowerCaseFast(string& str)
{
string res = "";
for(inti = 0; i < str.length(); i++) {
if(str[i] >= 'a'&& str[i] <= 'z')
res.push_back(str[i]);
}
returnres;
}
intmain()
{
string str = "Learn Competitive programming with GFG!";
Avoid using the + operator repeatedly when concatenating multiple strings. This can create unnecessary string objects, leading to poor performance. Instead, use StringBuilder (or StringBuffer for thread safety) to efficiently concatenate strings.
Java
importjava.io.*;
classGFG {
publicstaticvoidmain(String[] args)
{
// Slow Concatenation of Strings
String str1 = "";
str1 = str1 + "Hello";
str1 = str1 + " ";
str1 = str1 + "World";
System.out.println(str1);
// Fast Concatenation of Strings
StringBuilder str2 = newStringBuilder();
str2.append("Hello");
str2.append(" ");
str2.append("World");
System.out.println(str2);
}
}
Output
Hello World
Hello World
2. Use the equals() Method for String Comparison:
When comparing string content, use the equals() method or its variants (equalsIgnoreCase(), startsWith(), endsWith(), etc.) instead of the “==” operator, which compares object references.
Java
/*package whatever //do not write package name here */
importjava.io.*;
classGFG {
publicstaticvoidmain(String[] args)
{
String s1 = "GFG", s2 = "GFG";
// Incorrect implementation
System.out.println(s1 == s2);
System.out.println(newString("GFG")
== newString("GFG"));
// Correct Implementation
System.out.println(s1.equals(s2));
System.out.println(
newString("GFG").equals(newString("GFG")));
}
}
Output
true
false
true
true
Competitive Programming Tips for Strings in Python:
1. Use String Slicing and Concatenation Effectively.
String slicing is a powerful way to extract substrings from a string. You can use slicing to get individual characters, substrings of any length, or even reversed strings. String concatenation is used to join two or more strings together. There are two ways to concatenate strings in Python: using the + operator or the join() method. The + operator is more efficient for concatenating a small number of strings, while the join() method is more efficient for concatenating a large number of strings.
Python3
Str="Learn Competitive Programming "
print(f"First five characters ={Str[0:5]}")
print(f"Reverse ={Str[::-1]}")
Str+="with "
Str="".join([Str, "GFG!"])
print(Str)
Output
First five characters = Learn
Reverse = gnimmargorP evititepmoC nraeL
Learn Competitive Programming with GFG!
2. Use Regular Expressions for Pattern Matching:
Regular expressions are a powerful tool for matching patterns in strings. Python has a built-in re module that provides regular expression support.
Python3
importre
# Method to find the number of words using Regex
defcount_words(text):
words =re.findall(r"\w+", text)
returnlen(words)
print(count_words("Learn Competitive Programming with GFG!"))
Output
5
Important String Algorithms for Competitive Programming:
Here are some important string algorithms for competitive programming:
Learn to code easily with our course Coding for Everyone. This course is accessible and designed for everyone, even if you’re new to coding. Start today and join millions on a journey to improve your skills!Whether you’re preparing for your first job interview or aiming to upskill in this ever-evolving tech landscape, neveropen Courses are your key to success. We provide top-quality content at affordable prices, all geared towards accelerating your growth in a time-bound manner. Join the millions we’ve already empowered, and we’re here to do the same for you. Don’t miss out – check it out now!
