Strings
Common Methods & Operations
A cheat sheet of common methods and operations on strings. Take a look at the table below that
lists some common operations that can be performed on a string using built-in methods.
Method Description
str.length() Returns the length of the string str
str.charAt(n) Returns the character at the specified index
str.indexOf(ch) Returns the index of the first occurrence of character ch in the string.
str.substring(start, Returns a new string which is a substring of str beginning at start and exten
end) 1
str.toLowerCase() Converts string str to lower case
str.toUpperCase() Converts string str to upper case
str1.equals(str2) Compares the str1 with the str2 and returns true if both matches else false
Returns 0 if the str1 is equal to str2, negative value if the str1 is lexicograph
str1.compareTo(str2)
than str2 or value greater than 0 if the str1 is lexicographically greater than
Splits the string and returns the array of substrings that matches the given
str.split(regex)
expression.
str1.contains(str2) Returns true if str2 is found in string str1
str1.concat(str2) Combines strings str1 and str2
Reverse Words in a Sentence
Given a sentence (an array of characters), reverse the order of words.
Description
Reverse the order of words in a given sentence (an array of characters). Take the “Hello World”
string for example:
The "Hello World" string reversed should be "World Hello".
Solution
Here is how the solution works:
Reverse the string.
Traverse the string and reverse each word in place.
Let’s apply this solution to our example:
“The quick brown fox jumped over the lazy dog.”.
Reverse the string: “.god yzal eht revo depmuj xof nworb kciuq ehT”
Reverse each word in-place: “dog. lazy the over jumped fox brown quick The”
Code
class ReverseWords {
// Null terminating strings are not used in java
public static void strRev(char[] str, int start, int end) {
if (str == null || str.length < 2) {
return;
}
while (start < end) {
char temp = str[start];
str[start] = str[end];
str[end] = temp;
start++;
end--;
}
}
public static void reverseWords(char[] sentence) {
// Here sentence is a null-terminated string ending with char '\0'.
if (sentence == null || sentence.length == 0) {
return;
}
// To reverse all words in the string, we will first reverse
// the string. Now all the words are in the desired location, but
// in reverse order: "Hello World" -> "dlroW olleH".
int len = sentence.length;
strRev(sentence, 0, len - 2);
// Now, let's iterate the sentence and reverse each word in place.
// "dlroW olleH" -> "World Hello"
int start = 0;
int end;
while (true) {
// find the start index of a word while skipping spaces.
while (sentence[start] == ' ') {
++start;
}
if (start >= sentence.length - 1) {
break;
}
// find the end index of the word.
end = start + 1;
while (end < sentence.length - 1 && sentence[end] != ' ') {
++end;
}
// let's reverse the word in-place.
strRev(sentence, start, end - 1);
start = end;
}
}
static char[] getArray(String t) {
char[] s = new char[t.length() + 1];
int i = 0;
for (; i < t.length(); ++i) {
s[i] = t.charAt(i);
}
return s;
}
public static void main(String[] args) {
char[] s = getArray("Hello World!");
System.out.println(s);
reverseWords(s);
System.out.println(s);
}
}
Runtime complexity
The runtime complexity of this solution is linear, O(n). Position of all the elements in the sentence is
changed.
Memory complexity
The memory complexity of this solution is constant, O(1).
The solution reverses every word in-place i.e., it does not require any extra space.
Remove Duplicates from a String
Remove duplicate characters from a string which is passed by reference.
Description
Given a string that contains duplicate occurrences of characters, remove the duplicate occurrences.
The string is passed by reference. So you don’t need to return anything.
Solution
In this solution, we’ll keep two pointers or indices one for the current reading position and one for the
current writing position. Whenever we encounter the first occurrence of a character, we add it to the
HashSet. Any character already existing in the HashSet is skipped on any subsequent occurrence.
Below is an overview of the algorithm:
read_pos = 0
write_pos = 0
for each character 'c' in str
if 'c' not found in hashset
add 'c' to hashset
str[write_pos] = str[read_pos]
write_pos++
read_pos++
Code
class RemoveDuplicates {
// this solution uses extra memory
// to keep all characters present in string.
static void removeDuplicates(char[] str) {
Set<Character> hashset = new LinkedHashSet<Character> ();
int writeIndex = 0;
int readIndex = 0;
while (readIndex != str.length) {
if (!hashset.contains(str[readIndex])) {
hashset.add(str[readIndex]);
str[writeIndex] = str[readIndex];
++writeIndex;
}
++readIndex;
}
str[writeIndex] = '\0';
}
// Test Program
static char[] getArray(String t) {
char[] s = new char[t.length() + 1];
int i = 0;
for (; i < t.length(); ++i) {
s[i] = t.charAt(i);
}
s[i] = '\0';
return s;
}
static void print(char[] s) {
int i = 0;
while (s[i] != '\0') {
System.out.print(s[i]);
++i;
}
System.out.println();
}
public static void main(String[] args) {
char[] input = getArray("dabbac");
System.out.print("Before: ");
System.out.println(input);
RemoveDuplicates.removeDuplicates(input);
System.out.print("After: ");
print(input);
}
}
Runtime complexity
The runtime complexity of this solution is linear, O(n).
Memory complexity
The memory complexity of this solution is linear, O(n).
Solution 2
This algorithm does not require any extra memory. It maintains two pointers indices: one for the read
position and one for the write position. For every character in the input string that is present in the
sub-string [0, write_pos], we skip it; otherwise, we write the character at read_pos to write_pos.
Here is the algorithm:
read_pos = 0
write_pos = 0
while read_pos less than length(str)
if str[read_pos] not found in sub_string(0, write_pos)
str[write_pos] = str[read_pos]
++write_pos
++read_pos
Code
class RemoveDuplicates {
// this solution does not require any extra memory
// but runs in O(n^2) time
static void removeDuplicates(char[] str) {
if (str == null || str.length == 0) {
return;
}
int writeIndex = 0;
for (int i = 0; i < str.length; i++) {
boolean found = false;
for (int j = 0; j < writeIndex; j++) {
if (str[i] == str[j]) {
found = true;
break;
}
}
if (!found) {
str[writeIndex] = str[i];
writeIndex++;
}
}
if (writeIndex != str.length) {
str[writeIndex] = '\0';
}
}
/// Test Program.
static void print(char[] s) {
int i = 0;
while (s[i] != '\0') {
System.out.print(s[i]);
++i;
}
System.out.println();
}
static char[] getArray(String t) {
char[] s = new char[t.length() + 1];
int i = 0;
for (; i < t.length(); ++i) {
s[i] = t.charAt(i);
}
return s;
}
public static void main(String[] args) {
char[] input = getArray("dabbac");
System.out.print("Before: ");
System.out.println(input);
RemoveDuplicates.removeDuplicates(input);
System.out.print("After: ");
print(input);
}
}
Runtime complexity
The runtime complexity of this solution is quadratic, O(n^2).
Memory complexity
The memory complexity of this solution is constant, O(1).
Remove White Spaces from a String
Given a null terminated string, remove any white spaces (tabs or spaces).
Description
Given a null terminated string, remove any white spaces (tabs or spaces). For example:
All greek to me. After removing the white spaces, the string should look like this:
Allgreektome.
Solution
This problem can be solved with two pointers. Here is an overview:
read_ptr and write_ptr initialized to start of string, str[0]
With the read_ptr, iterate over the input string reading one character at a time.
While moving read_ptr towards the end of the array:
if read_ptr points to a white space, skip
if read_ptr points to any other character, write that to write_ptr and increment the
write_ptr.
Terminate the loop when the read_ptr reaches the end of the string.
At this point, the write_ptr will point to the string with all white spaces removed.
Code
class RemoveSpaces {
static boolean isWhiteChar(char c) {
// there can be more white space characters
// but for simplicity lets assume that we have
// only two white space character
// i.e. space and tab
if (c == ' ' || c == '\t') {
return true;
}
return false;
}
static void removeWhiteSpaces(char[] s) {
if (s == null || s.length == 0 || s[0] == '\0') {
return;
}
// We will use read, write pointers here.
// Write pointer will follow the read pointer
// and only write characters read that are neither
// a space (' ') nor a tab ('\t').
int readPtr = 0;
int writePtr = 0;
while (readPtr < s.length) {
// Lets assume there are only two white
// space characters: space and tab.
if (!isWhiteChar(s[readPtr])) {
s[writePtr] = s[readPtr];
++writePtr;
}
++readPtr;
}
// Let's mark the end of string.
s[writePtr] = '\0';
}
static void print(char[] s) {
int i = 0;
while (i < s.length && s[i] != '\0') {
System.out.print(s[i]);
++i;
}
System.out.println();
}
static char[] getArray(String t) {
char[] s = new char[t.length()];
int i = 0;
for (; i < t.length(); ++i) {
s[i] = t.charAt(i);
}
return s;
}
public static void main(String[] args) {
char[] s = getArray("All greek to me");
System.out.print("Before: ");
print(s);
removeWhiteSpaces(s);
System.out.print("After: ");
print(s);
}
}
Runtime complexity
The runtime complexity of this solution is linear, O(n).
Memory complexity
The memory complexity of this solution is linear, O(1).
Word Break Problem
Given a dictionary of words and an input string tell whether the input string can be completely
segmented into dictionary words.
Description
We are given a dictionary of words and a large input string. We have to find out whether the input
string can be completely segmented into the words of a given dictionary. The following two examples
elaborate on the problem further.
Solution
We can solve this problem by segmenting the large string at each possible position to see if the
string can be completely segmented to words in the dictionary. If we write the algorithm in steps it
will be as follows:
n = length of input string
for i = 0 to n - 1
first_word = substring (input string from index [0, i] )
second_word = substring (input string from index [i + 1, n - 1] )
if dictionary has first_word
if second_word is in dictionary OR second_word is of zero length, then return true
recursively call this method with second_word as input and return true if it can be
segmented
The algorithm will compute two strings from scratch in each iteration of the loop. Worst case
scenario, there would be a recursive call of the second_word each time. This shoots the time
complexity up to 2^n.
Code
class StringSegmentation {
public static boolean canSegmentString(String s, Set <String> dictionary) {
for (int i = 1; i <= s.length(); ++i) {
String first = s.substring(0, i);
if (dictionary.contains(first)) {
String second = s.substring(i);
if (second == null || second.length() == 0 || dictionary.contains(second) ||
canSegmentString(second, dictionary)) {
return true;
}
}
}
return false;
}
public static void main(String[] args) {
Set < String > dictionary = new HashSet < String > ();
String s = new String();
s = "hellonow";
dictionary.add("hello");
dictionary.add("hell");
dictionary.add("on");
dictionary.add("now");
if (canSegmentString(s, dictionary)) {
System.out.println("String Can be Segmented");
} else {
System.out.println("String Can NOT be Segmented");
}
}
}
You can see that we may be computing the same substring multiple times, even if it doesn’t exist in
the dictionary. This redundancy can be fixed by memoization, where we remember which substrings
have already been solved To achieve memoization, we can store the second string in a new set each
time.This will reduce both time and memory complexities.
Runtime complexity
The runtime complexity of this solution is exponential, O(2^n), if we use only recursion.
With memoization, the runtime complexity of this solution can be improved to be polynomial, O(n^2).
Memory complexity
The memory complexity of this solution is polynomial, O(n^2).
Memory Complexity is O(n^2), because we create a substring on each recursion call. Creating a
substring can be avoided if we pass indices.
Find all Palindrome Substrings
Given a string, find all substrings that are palindromes.
Description
Given a string find all non-single letter substrings that are palindromes.
Solution
You can see that we may be computing the same substring multiple times, even if it doesn’t exist in
the dictionary. This redundancy can be fixed by memoization, where we remember which substrings
have already been solved To achieve memoization, we can store the second string in a new set each
time.This will reduce both time and memory complexities. A palindrome is a word, phrase, number,
or other sequence of characters which reads the same backwards as it reads forwards. A naive
solution of this problem is to find all substrings of a given string and check whether each substring is
a palindrome or not. This solution has a complexity of O(n^3).
Code
class PalindromeSubStrings{
public static boolean isPalindrome(String input, int i, int j) {
while(j > i){
if(input.charAt(i) != input.charAt(j))
return false;
i++;
j--;
}
return true;
}
public static int findAllPalindromeSubstrings(String input) {
int count = 0;
for(int i = 0 ; i < input.length() ; i++) {
for(int j = i + 1 ; j < input.length() ; j++) {
if(isPalindrome(input,i,j)){
System.out.println(input.substring(i,j+1));
count++;
}
}
}
return count;
}
public static void main(String[] args) {
String str = "aabbbaa";
int count = findAllPalindromeSubstrings(str);
System.out.println("Total palindrome substrings: " + count);
}
}
Runtime complexity
The runtime complexity of this solution is polynomial, O(n^3).
Memory complexity
The memory complexity of this solution is constant, O(1).
Solution 2
We can reduce the runtime complexity of this algorithm to O(n^2) from O(n^3) by using the following
approach. For each letter in the input string, start expanding to the left and right while checking for
even and odd length palindromes. Move to the next letter if we know a palindrome doesn’t exist. We
expand one character to the left and right and compare them. If both of them are equal, we print out
the palindrome substring.
Code
class PalindromeSubStrings{
public static int findPalindromesInSubString(String input, int j, int k) {
int count = 0;
for (; j >= 0 && k < input.length(); --j, ++k) {
if (input.charAt(j) != input.charAt(k)) {
break;
}
System.out.println(input.substring(j, k+1));
count++;
}
return count;
}
public static int findAllPalindromeSubstrings(String input) {
int count = 0;
for(int i = 0 ; i < input.length() ; ++i) {
count+= findPalindromesInSubString(input, i-1, i+1);
count+= findPalindromesInSubString(input, i, i+1);
}
return count;
}
public static void main(String[] args) {
String str = "aabbbaa";
int count = findAllPalindromeSubstrings(str);
System.out.println("Total palindrome substrings: " + count);
}
}
Runtime complexity
The runtime complexity of this solution is polynomial, O(n^2).
Memory complexity
The memory complexity of this solution is constant, O(1).
Balanced Parentheses
Problem Statement
For a given number ‘N’, write a function to generate all combination of ‘N’ pairs of balanced
parentheses.
Example 1
Input: N=2 Output: (()), ()()
Example 2
Input: N=3 Output: ((())), (()()), (())(), ()(()), ()()()
Basic Solution
This problem follows the Subsets pattern and can be mapped to Permutations. We can follow a
similar BFS approach. Let’s take Example-2 mentioned above to generate all the combinations of
balanced parentheses. Following a BFS approach, we will keep adding open parentheses ( or close
parentheses ). At each step we need to keep two things in mind:
We can’t add more than ‘N’ open parenthesis.
To keep the parentheses balanced, we can add a close parenthesis ) only when we have
already added enough open parenthesis (. For this, we can keep a count of open and close
parenthesis with every combination.
Following this guideline, let’s generate parentheses for N=3:
Start with an empty combination: “”
At every step, let’s take all combinations of the previous step and add ( or ) keeping the
above-mentioned two rules in mind.
For the empty combination, we can add ( since the count of open parenthesis will be less
than ‘N’. We can’t add ) as we don’t have an equivalent open parenthesis, so our list of
combinations will now be: “(”
For the next iteration, let’s take all combinations of the previous set. For “(” we can add
another ( to it since the count of open parenthesis will be less than ‘N’. We can also add ) as
we do have an equivalent open parenthesis, so our list of combinations will be: “((”, “()”
In the next iteration, for the first combination “((”, we can add another ( to it as the count of
open parenthesis will be less than ‘N’, we can also add ) as we do have an equivalent open
parenthesis. This gives us two new combinations: “(((” and “(()”. For the second combination
“()”, we can add another ( to it since the count of open parenthesis will be less than ‘N’. We
can’t add ) as we don’t have an equivalent open parenthesis, so our list of combinations will
be: “(((”, “(()”, ()("
Following the same approach, next we will get the following list of combinations: “((()”, “(()(”,
“(())”, “()((”, “()()”
Next we will get: “((())”, “(()()”, “(())(”, “()(()”, “()()(”
Finally, we will have the following combinations of balanced parentheses: “((()))”, “(()())”, “(())
()”, “()(())”, “()()()”
We can’t add more parentheses to any of the combinations, so we stop here.
Code
import java.util.*;
class ParenthesesString {
String str;
int openCount; // open parentheses count
int closeCount; // close parentheses count
public ParenthesesString(String s, int openCount, int closeCount) {
str = s;
this.openCount = openCount;
this.closeCount = closeCount;
}
}
class GenerateParentheses {
public static List<String> generateValidParentheses(int num) {
List<String> result = new ArrayList<String>();
Queue<ParenthesesString> queue = new LinkedList<>();
queue.add(new ParenthesesString("", 0, 0));
while (!queue.isEmpty()) {
ParenthesesString ps = queue.poll();
// if we've reached the maximum number of open and close parentheses, add to the result
if (ps.openCount == num && ps.closeCount == num) {
result.add(ps.str);
} else {
if (ps.openCount < num) // if we can add an open parentheses, add it
queue.add(new ParenthesesString(ps.str + "(", ps.openCount + 1, ps.closeCount));
if (ps.openCount > ps.closeCount) // if we can add a close parentheses, add it
queue.add(new ParenthesesString(ps.str + ")", ps.openCount, ps.closeCount + 1));
}
}
return result;
}
public static void main(String[] args) {
List<String> result = GenerateParentheses.generateValidParentheses(2);
System.out.println("All combinations of balanced parentheses are: " + result);
result = GenerateParentheses.generateValidParentheses(3);
System.out.println("All combinations of balanced parentheses are: " + result);
}
}
Let’s try to estimate how many combinations we can have for ‘N’ pairs of balanced parentheses. If
we don’t care for the ordering - that ) can only come after ( - then we have two options for every
position, i.e., either put open parentheses or close parentheses. This means we can have a
maximum of 2^N combinations. Because of the ordering, the actual number will be less than 2^N
Time complexity
You will realize that, in the worst case, it is equivalent to a binary tree, where each node will have
two children. This means that we will have 2^N leaf nodes and 2^N-1 intermediate nodes. So the
total number of elements pushed to the queue will be 2^N + 2^N −1, which is asymptotically
equivalent to O(2^N). While processing each element, we do need to concatenate the current string
with ( or ). This operation will take O(N), so the overall time complexity of our algorithm will
be O(N2^N)*. This is not completely accurate but reasonable enough to be presented in the
interview.
The actual time complexity (O(4^n/sqrt{n}) is bounded by the Catalan number and is beyond the
scope of a coding interview.
Space complexity
All the additional space used by our algorithm is for the output list. Since we can’t have more
than O(2^N) combinations, the space complexity of our algorithm is O(N2^N)*.
Recursive Solution
Here is the recursive algorithm following a similar approach:
import java.util.*;
class GenerateParenthesesRecursive {
public static List<String> generateValidParentheses(int num) {
List<String> result = new ArrayList<String>();
char[] parenthesesString = new char[2 * num];
generateValidParenthesesRecursive(num, 0, 0, parenthesesString, 0, result);
return result;
}
private static void generateValidParenthesesRecursive(int num, int openCount, int closeCount,
char[] parenthesesString, int index, List<String> result) {
// if we've reached the maximum number of open and close parentheses, add to the result
if (openCount == num && closeCount == num) {
result.add(new String(parenthesesString));
} else {
if (openCount < num) { // if we can add an open parentheses, add it
parenthesesString[index] = '(';
generateValidParenthesesRecursive(num, openCount + 1, closeCount, parenthesesString,
index + 1, result);
}
if (openCount > closeCount) { // if we can add a close parentheses, add it
parenthesesString[index] = ')';
generateValidParenthesesRecursive(num, openCount, closeCount + 1, parenthesesString,
index + 1, result);
}
}
}
public static void main(String[] args) {
List<String> result = GenerateParenthesesRecursive.generateValidParentheses(2);
System.out.println("All combinations of balanced parentheses are: " + result);
result = GenerateParenthesesRecursive.generateValidParentheses(3);
System.out.println("All combinations of balanced parentheses are: " + result);
}
}
Longest Substring with Distinct
Characters
Given a string, find the length of the longest substring, which has all distinct characters.
Example 1
Input: String="aabccbb" Output: 3 Explanation: The longest substring with distinct characters is
"abc".
Example 1
Input: String="abbbb" Output: 2 Explanation: The longest substring with distinct characters is "ab".
Solution
This problem follows the Sliding Window pattern, and we can use a similar dynamic sliding window
strategy as discussed in Longest Substring with K Distinct Characters. We can use a HashMap to
remember the last index of each character we have processed. Whenever we get a duplicate
character, we will shrink our sliding window to ensure that we always have distinct characters in the
sliding window.
Code
import java.util.*;
class NoRepeatSubstring {
public static int findLength(String str) {
int windowStart = 0, maxLength = 0;
Map<Character, Integer> charIndexMap = new HashMap<>();
// try to extend the range [windowStart, windowEnd]
for (int windowEnd = 0; windowEnd < str.length(); windowEnd++) {
char rightChar = str.charAt(windowEnd);
// if the map already contains the 'rightChar', shrink the window from the beginning so that
// we have only one occurrence of 'rightChar'
if (charIndexMap.containsKey(rightChar)) {
// this is tricky; in the current window, we will not have any 'rightChar' after its previous index
// and if 'windowStart' is already ahead of the last index of 'rightChar', we'll keep 'windowStart'
windowStart = Math.max(windowStart, charIndexMap.get(rightChar) + 1);
}
charIndexMap.put(rightChar, windowEnd); // insert the 'rightChar' into the map
maxLength = Math.max(maxLength, windowEnd - windowStart + 1); // remember the
maximum length so far
}
return maxLength;
}
public static void main(String[] args) {
System.out.println("Length of the longest substring: " +
NoRepeatSubstring.findLength("aabccbb"));
System.out.println("Length of the longest substring: " +
NoRepeatSubstring.findLength("abbbb"));
System.out.println("Length of the longest substring: " +
NoRepeatSubstring.findLength("abccde"));
}
}
Time Complexity
The above algorithm’s time complexity will be O(N), where ‘N’ is the number of characters in the
input string.
Space Complexity
The algorithm’s space complexity will be O(K)O(K), where KK is the number of distinct characters in
the input string. This also means K<=NK<=N, because in the worst case, the whole string might not
have any duplicate character, so the entire string will be added to the HashMap. Having said that,
since we can expect a fixed set of characters in the input string (e.g., 26 for English letters), we can
say that the algorithm runs in fixed space O(1)O(1); in this case, we can use a fixed-size array
instead of the HashMap.
