Introduction to Strings – Data Structure and Algorithm Tutorials
A string is a sequence of characters, often used to represent text. In programming, strings are a common data type and are used for a variety of tasks, such as representing names, addresses, and other types of information.
- Substring extraction
- Length calculation
- Searching for a pattern
- Replacing a substring
- Character arrays
- String objects in object-oriented programming languages
- Knuth-Morris-Pratt (KMP) algorithm for pattern matching
- Rabin-Karp algorithm for pattern matching
- Z algorithm for pattern matching
- Manacher’s algorithm for finding the longest palindromic substring
- Suffix Array and Suffix Tree for string processing tasks
- Text processing
- URL parsing
- Storing and manipulating human-readable data.
What is String?
Strings are considered a data type in general and are typically represented as arrays of bytes (or words) that store a sequence of characters. Strings are defined as an array of characters. The difference between a character array and a string is the string is terminated with a special character ‘\0’
Below are some examples of strings:
“geeks” , “for”, “geeks”, “GeeksforGeeks”, “Geeks for Geeks”, “123Geeks”, “@123 Geeks”
How String is represented in Memory?
In C, a string can be referred to either using a character pointer or as a character array. When strings are declared as character arrays, they are stored like other types of arrays in C. For example, if str is an auto variable then the string is stored in the stack segment, if it’s a global or static variable then stored in the data segment, etc.
How to Declare Strings in various languages?
Below is the representation of strings in various languages:
General Operations performed on String:
Here we are providing you with some must-know concepts of string:
1. Concatenation of Strings
The process of combining more than one string together is known as Concatenation. String Concatenation is the technique of combining two strings.
There are two ways to concatenate two strings:
a) String concatenation without using any inbuilt methods:
Below is the algorithm for the Concatenation of two strings:
Algorithm: CONCATENATE (STR1, STR2, STR3)
1. LEN1 = LENGTH(STR1). 2. LEN2 = LENGTH(STR2). 3. SET I = 0. 4. Repeat Steps 5 and 6 while I < LEN1-1: 5. STR3[I] = STR1[I]. 6. SET I = I+1. 7. SET J = 0. 8. Repeat Steps 9 to 11 while I < (LEN1 + LEN2 - 2): 9. STR3[I] = STR2[J]. 10. J = J+1. 11. I = I+1. 12.Exit.
b) String concatenation using inbuilt methods:
- String concatenation in C/C++
- String concatenation in Java
- String concatenation in Python
- String concatenation in C#
2. Find in String
A very basic operation performed on Strings is to find something in the given whole string. Now, this can be to find a given character in a string, or to find a complete string in another string.
a) Find a character in string:
Given a string and a character, your task is to find the first position of the character in the string. These types of problems are very competitive programming where you need to locate the position of the character in a string.
b) Find a substring in another string:
Consider there to be a string of length N and a substring of length M. Then run a nested loop, where the outer loop runs from 0 to (N-M) and the inner loop from 0 to M. For every index check if the sub-string traversed by the inner loop is the given sub-string or not.
An efficient solution is to use a O(n) searching algorithm like KMP algorithm, Z algorithm, etc.
3. Replace in String
Many times, it is very important to make corrections in strings. Replacing a character, word or phrase in a String is another very common operation performed on Strings.
The simplest approach to solve the given problem is to traverse the string S and when any string S1 is found as a substring in the string S then replace it by S2. Follow the steps below to solve this problem:
- Initialize a string ans to store the resultant string after replacing all the occurrences of the substring S1 to S2 in the string S.
- Iterate over the characters of the string S using variable i and perform the following steps:
- If the prefix substring of the string S is equal to S1 from the index i, then add the string S2 in the string ans.
- Otherwise, add the current character to the string ans.
- After completing the above steps, print the string ans as the result.
4. Finding the Length of String
One of the most general operations on String is to find the length/size of a given string. Length is defined as the number of characters in a string is called the length of that string.
There are two ways to concatenate two strings:
a) Length of string without using any inbuilt methods:
Below is the algorithm for finding the length of two strings:
1. SET LEN = 0 AND I = 0. 2. Repeat Steps 3 to 4 while STRING[I] is not NULL: 3. LEN = LEN + 1. 4. SET I = I + 1. 5. Exit.
b) Length of string using inbuilt methods:
- Length of string in C
- Length of string in C++
- Length of string in Java
- Length of string in Python
- Length of string in C#
5. Trim a String
Spaces or special characters are very common in Strings. So it is important to know how to trim such characters in String.
Below is a Simple Solution
1) Iterate through all characters of given string, do following
a) If current character is a space, then move all subsequent characters one position back and decrease length of the result string.
The time complexity of the above solution is O(n2).
A Better Solution can solve it in O(n) time. The idea is to keep track of count of non-space character seen so far.
1) Initialize ‘count’ = 0 (Count of non-space character seen so far)
2) Iterate through all characters of given string, do following
a) If current character is non-space, then put this character at index ‘count’ and increment ‘count’
3) Finally, put ‘\0’ at index ‘count’
6. Reverse and Rotation of a String
Reverse operation is interchanging the position of characters of a string such that the first becomes the last, the second becomes the second last, and so on.
a) Rotations of a String:
Consider a string “geeks”, now all possible rotations for this will be:
b) Reverse a String:
The reversing of a string is nothing but simply substituting the last element of a string to the 1st position of the string.
7. Subsequence of a String
A subsequence is a sequence that can be derived from another sequence by removing zero or more elements, without changing the order of the remaining elements.
More generally, we can say that for a sequence of size n, we can have (2n-1) non-empty sub-sequences in total.
For example, Consider the string “geeks”, there are 15 sub-sequences.
g, e, e, k, s, ge, ge, gk, gs, ee, ek, es, ek, es, ks, gee, gek, ges, gek, ges, gks, eek, ees, eks, eks, geek, gees, eeks, geeks
8. Substring of a String
A substring is a contiguous part of a string, i.e., a string inside another string.
In general, for a string of size n, there are n*(n+1)/2 non-empty substrings.
For example, Consider the string “geeks”, There are 15 non-empty substrings.
The subarrays are:
g, ge, gee, geek, geeks, e, ee, eek, eeks, e, ek, eks, k, ks, ks
9. Binary String
A Binary String is a special kind of string made up of only two types of characters, such as 0 and 1.
Input: str = "01010101010" Output: Yes, it is a Binary String Input: str = "geeks101" Output: No, it is not a Binary String
10. Palindrome String
A string is said to be a palindrome if the reverse of the string is the same as the string.
“abba” is a palindrome, but “abbc” is not a palindrome.
11. Lexicographic Patterns
Lexicographical pattern is the pattern based on the ASCII value or can be said in dictionary order. We consider the lexicographic order of characters as their order of ASCII value. Hence the lexicographical order of characters will be
‘A’, ‘B’, ‘C’, …, ‘Y’, ‘Z’, ‘a’, ‘b’, ‘c’, …, ‘y’, ‘z’.
12. Pattern Searching
Pattern searching is searching a given pattern in the string. It is an advanced topic of string. The Pattern Searching algorithms are sometimes also referred to as String Searching Algorithms and are considered as a part of the String algorithms. These algorithms are useful in the case of searching a string within another string.
Top Theoretical Interview Questions
|1||What are different ways to create String Object?||View|
|2||Can we compare String using the == operator? What is the risk?||View|
|3||How to replace a substring with ( from a string ?||View|
|4||What is the difference between String and StringBuffer in java?||View|
|5||How do I convert a string version of a number in an arbitrary base to an integer?||View|
|6||How do you compare two Strings in Java?||View|
|7||What is String in Data Structures?||View|
|8||What is the difference between Strings vs. Char arrays?||View|
|9||What is a null-terminated String?||View|
|10||Reverse a String using Stack||View|
|11||Difference between String, StringBuffer and StringBuilder?||View|
|12||Why String is immutable or final in Java||View|
|13||What Is the String Constant Pool?||View|
|14||Remove Invalid Parentheses||View|
|15||What is the use of the substring() method?||View|
|16||Explain how can I remove the trailing spaces from a String||View|
|17||Explain how can I pad a string to known length||View|
|18||Explain how can you tell whether two string are the same||View|
|19||How to check if the String is empty?||View|
|20||Can we use a string in the switch case in java?||View|
|21||How string concatenation using the + operator works in Java?||View|
|22||What are the different string methods in Java?||View|
|23||What do you mean by StringJoiner?||View|
|24||How to convert string representation of list to a list?||View|
|26||How do I tokenize a string in C++?||View|
|27||Print all permutations of the String ?||View|
|28||How do you reverse a given string in place?||View|
|29||How to convert a byte array to String?||View|
|30||How to calculate total number of vowels in String?||View|
|31||Write a program to convert a string in lowercase||View|
|32||Write a program to convert a string in uppercase.||View|
|33||Write a C++ program to find the length of the string.||View|
|34||In what way should two whether they are anagrams?strings be compared to determine||View|
|35||Write a java program to tOGGLE each word in string?||View|
|36||How to convert String to Date in java?||View|
|37||Java Program to reverse a given String with preserving the position of space||View|
|38||Multiply Large Numbers represented as Strings||View|
|39||String “indexOf” Method||View|
Top 50 interview coding question
Easy Problems on String
Medium Problems on String
Hard Problems on String
Advantages of using String:
- Strings provide us very helpful string algorithms for solving very complex problems with less time complexity.
- String provides us a string library to create string objects which will allow strings to be dynamically allocated and also boundary issues are handled inside class library.
- String helps as a base for many data structures such as tries, suffix trees, suffix arrays, ternary search trees, and much more.
- String provides us various inbuilt functions under string library such as sort(), substr(i, j), compare(), push_back() and many more.
- In C language strings can have compile-time allocation and determination of size. This makes them more efficient, faster run-time at the time of using them.
- In C++ we do not need to predefine the size of a string.
Disadvantages of String:
- Strings are generally slow in performing operations like input, output.
- In JAVA strings are immutable they cannot be modified or changed
- In JAVA you cannot extend string class which means overriding methods in string class is not possible.
- C strings are fixed in size and are not dynamic.
Application of String:
- Information Retrieval: String applications help us to retrieve information from unknown data sources( large datasets used as input) along with the help of string matching/retrieval module helps us to retrieve important information.
- Encoding/Decoding(Cipher Text Generation): Strings can be used for encoding and decoding for the safe transfer of data from sender to receiver to make sure no one in the way of transmission gets to read your data as they could perform both active and passive attacks. The text you transfer as a message gets ciphered at the sender’s end and decoded at the receiver’s end.
- Plagiarism Checker: Strings can be used to find Plagiarism in codes, and contents in a very little amount of time using string matching algorithms. Using this the computer could easily tell us the percentage of code, and text written by any two users matches by how much percent.
- Improved Filters For The Approximate Suffix-Prefix Overlap Problem: Strings and its algorithms applications help us to provide improved Filters for the Approximate Suffix-Prefix Overlap Problem. The approximate suffix-prefix overlap problem is to find all pairs of strings from a given set such that a prefix of one string is similar to a suffix of the other.
Real-Time Application of String:
- Search Engines: Strings can be used in many search engine techniques. Most of the data are available on the internet in the form of textual data. Due to huge amount of uncategorized text data, it becomes really difficult to search a particular content. Web search engines organize the data and categorize the data string matching algorithms.
- Intrusion Detection System: Strings can be used in intrusion detection systems. Packets that contain intrusion-related keywords are found by applying string matching algorithms.
- Bioinformatics: Strings can be used in the field of Bioinformatics( DNA sequencing). String matching module can be used to solve issues or problems regarding genetic sequences and to find the patterns in DNA.
- Spam Detection: Strings can be used to serve as a spam detection system as the concept of string matching algorithm will be applied here. Spam (unwanted emails) could cause great financial loss. All the spam filters use the concept of string matching to identify and discard the spam.
Important points about strings:
- Strings are immutable in many programming languages.
- Strings are often used to store and manipulate human-readable data.
- String operations such as concatenation, substring extraction, length calculation, comparison, pattern matching, and sorting can be implemented in various ways with different time and space complexities.
- Efficient algorithms such as Knuth-Morris-Pratt (KMP), Rabin-Karp, Z algorithm, Manacher’s algorithm, Suffix Array, and Suffix Tree exist for string processing tasks.
- Strings can be implemented as character arrays or as objects in object-oriented programming languages.
- Strings have wide range of applications in text processing, URL parsing, and other areas where human-readable data is stored and manipulated.
Frequently asked questions (FAQs) on String
1. Is string a linear data structure?
Yes, string is a linear data structure.
2. Where are strings used?
It is used to store the sequence of characters.
3. Is string a data type?
A string is generally considered a data type and is often implemented as an array data structure of bytes (or words) that stores a sequence of elements, typically characters, using some character encoding.
4. Why is text called string?
Text are also called string because it consists of sequence of characters like string.
5. What are characters in a string?
Each digit in a string is a character and character is a single visual object used to represent text, numbers, or symbols.
After the discussion, we concluded that Strings are a simple method to store some textual information and Strings are an array of characters that terminate with a null character ‘\0’. The difference between a character array and a string is that, unlike the character array, the string ends with a null character. Apart from this we have also discussed Top theoretical interview questions as well as Top 50 interview coding question on string which will help you to tackle interview problems.
- Complete Guide on Arrays Interview Preparation
- Top Data Structures That Every Programmer Must Know
- SDE SHEET – A Complete Guide for SDE Preparation
- Amazon SDE Sheet – A Guide for Amazon SDE Interview Preparation
- Google Interview Preparation For Software Engineer – A Complete Guide
Please Login to comment...