# Top 20 String Algorithm Questions from Coding Interviews

In this article, we are going to see top 20 String based coding interview question and their solution to help programmers better prepare for interviews. The string is one of the most important data structure and available in almost every programming language like Java, C, C++, Python, Perl, and Ruby. Though there implement differ the essence remains same like String is NULL terminated character array in C but String is an object in Java, again backed by character array. The string is also available on weekly typed languages like Python and Perl.  This is why you will always find some String based coding question on programming interview.

Even in your college days, you would have solved lots of coding problems based upon String like reversing String in place, checking if String is a palindrome, checking if two strings are an anagram of each other, calculating permutations of String etc.

The coding questions from programming interviews are also not very different from that, but yes it gets slightly more difficult with your experience.

For example, in your first few programming job interviews, you may find questions like removing duplicates from String or replacing all spaces with %20, but as you get more experience and apply for senior developer position, you can expect tough questions about how to find the longest palindrome in a string or printing all permutations of String etc.

This article contains both easy and difficult String coding questions for your preparation. I have not posted the solution right behind the problem so that you can give it a shot before checking the solution. You can solve these String based coding question on any language of your choice like C, C++, Java, Python or even JavaScript.

Btw, if you are new to Data Structure and Algorithms or want to revise fundamental algorithms before interviews, I suggest you join a comprehensive course like Data Structures and Algorithms: Deep Dive Using Java on Udemy. It's one of the best course and covers both basic algorithms and data structure like the array, linked list, binary tree but also advanced concepts like bucket sort, counting sort and other O(n) sorting algorithms.

## 20 String Algorithm based Coding Interview Questions

Here is my collection of some of the most frequently asked String based coding questions from programming interview. Remember, there are many algorithms to solve the same problem, and you should know that, mainly to handle the follow-up question better.

Also remember to solve the same question using both recursion and iteration, as interviewer really like to ask iterative version if you come up with a recursive algorithm and vice-versa.

Nevertheless, if you see your favorite question is not included in the list, feel free to suggest, I will include it.

You can also post question asked to you on your interview and you have not found its solution yet. Some questions are still unsolved or solution is not yet posted on my blog. Also, the difficulty level increases as you move questions.

#### 1) How to Print duplicate characters from String? (solution)

To start with, we have a simple String related coding question frequently asked in programming interviews. You need to write a program in JavaCC++Python, Perl, or Ruby to print duplicate characters from a given String.

For example, if String is "Java" then the program should print "a". Bonus points if your program is robust and handles different kinds of input e.g. String without duplicate, null or empty String etc. Bonus points if you also write unit tests for normal and edge cases.

#### 2) How to check if two Strings are anagrams of each other? (solution)

A simple coding problem based upon String, but could also be asked with numbers. You need to write a Java program to check if two given strings are anagrams of Each other. Two strings are anagrams if they are written using the same exact letters, ignoring space, punctuation, and capitalization. Each letter should have the same count in both strings. For example, the Army and Mary are an anagram of each other.

#### 3) How to program to print first non repeated character from String? (solution)

One of the most common string interview questions: Find the first non-repeated (unique) character in a given string. for Example, if given String is "Morning" then it should print "M". This question demonstrates the efficient use of the hash table data structure.

We scan the string from left to right counting the number occurrences of each character in a Hashtable. Then we perform a second pass and check the counts of every character. Whenever we hit a count of 1 we return that character, that’s the first unique letter. Be prepared for follow-up question for improving memory efficiency, solving it without the hash table as well.

Btw, if you are not familiar with hash table and other essential data structure then you should first go through a beginners algorithms course like Algorithms and Data Structures - Part 1 and 2 on Pluralsight which not only teach you basic data structure and algorithms but also how to calculate time and space complexity which is key for doing well on interviews.

#### 4) How to reverse String in Java using Iteration and Recursion? (solution)

Your task is to write a program to reverse String in Java without using StringBuffer class. You also need to provide both iterative and recursive algorithm for String reversal. You can use other String utility methods e.g. charAt()toCharArray() or substring() from java.lang.String class.

#### 5) How to check if a String contains only digits?  (solution)

You need to write a program to check a String contains only numbers by using Regular expression in Java. You can use Java API but a solution without using Java API will be better because that is what interviewer can always ask.

#### 6) How to find duplicate characters in a String? (solution)

You need to write a program to print all duplicate character and their count in Java. For example, if given String is "Programming" then your program should print
g : 2
r : 2
m : 2

#### 7) How to count a number of vowels and consonants in a String? (solution)

One of easiest String question you will ever see. You have to write a Java program which will take a String input and print out a number of vowels and consonants on that String. For example, if the input is "Java" then your program should print "2 vowels and 2 consonants".

If you get this question on Interview, you should clarify whether String can contain numbers, special characters or not like anything other than vowels and consonants.

This is an important tip for doing well on interviews. I also suggest revising essential data structure before interviews by joining Data Structures in Java: An Interview Refresher course on Educative.

#### 8) How to count the occurrence of a given character in String? (solution)

If the interviewer asks you to count the occurrence of more than one character than you can either use an array, hash table or any additional data structure. In order to solve this problem, you are not allowed to do so. Your method must return a count of a given character, for example, if input String is "Java" and given character is 'a' then it should return 2. Bonus point if you handle case, null and empty String and come up with unit tests.

#### 9) How to convert numeric String to an int? (solution)

A classical coding interview question based upon String. You need to write a method like atoi() from C/C++, which takes a numeric String and return its int equivalent. For example, if you pass "67263" to the program then it should return 67263.

Make sure your solution is robust like it should be able to handle + and - character, null and empty String, integer overflow and other corner cases.  Bonus points if you come up with good unit test cases.

By the way, if your interviewer doesn't mention to you about atoi() then you can also use Java API's parseInt() or valueOf() method to solve this problem.

#### 10) How to replace each given character to other e.g. blank with %20? (solution)

Write a Java program to replace a given character in a String to other provided character, for example, if you are asked to replace each blank in a String with %20, similar to URL encoding done by the browser so that Server can read all request parameters. For example, if the input is "Java is Great" and asked to replace space with %20 then it should be "Java%20is%20Great".

#### 11) How to find all permutations of String? (solution)

I have seen this String interview question on many interviews. It has an easy recursive solution but things get really tricky when Interviewer asks you to solve this question without using recursion. You can use a Stack though. Write a program to print all permutations of a String in Java, for example, the if input is "xyz" then it should print "xyz""yzx""zxy""xzy""yxz""zyx".

#### 12) How to reverse words in a sentence without using a library method? (solution)

Write a function, which takes a String word and returns sentence on which words are reversed in order like if the input is "Java is best programming language", the output should be "language programming best is Java".

#### 13) How to check if String is Palindrome? (solution)

Another easy coding question based upon String, I am sure you must have done this numerous time. Your program should return true if String is a Palindrome, otherwise false. For example, if the input is "radar", the output should be true, if the input is "madam" output will be true, and if the input is "Java" output should be false.

#### 14) How to remove duplicate characters from String? (solution)

This is one of the interesting String question, which also has lots of variants. You need to remove duplicate characters from a given string keeping only the first occurrences. For example, if the input is ‘bananas’ the output will be ‘bans’. Pay attention to what output could be, because if you look closely original order of characters are retained the in output.

This is where many developers make the mistake of shorting character array of String and removing duplicates, similar to how you remove duplicates from an array. That destroys the original order of characters and will not be the correct solution in this case.

#### 15) How to check if a String is a valid shuffle of two String? (solution)

One more difficult String algorithm based coding question for senior developers. You are given 3 strings: first,  second, and third.  Third String is said to be a shuffle of first and second if it can be formed by interleaving the characters of first and second String in a way that maintains the left to right ordering of the characters from each string.

For example, given first = "abc" and second = "def",  third = "dabecf"  is a valid shuffle since it preserves the character ordering of the two strings. So, given these 3 strings write a function that detects whether the third String is a valid shuffle of first and second String.

#### 16) Write a program to check if a String contains another String like indexOf ()? (solution)

You need to write a function to search for the existence of a string (target) in another string (source). The function takes two strings as the input and returns the index where the second string is found. If the target string cannot be found, then return -1.

If you are a Java developer, then you can relate its behavior to indexOf() method from java.lang.String class. This question is also asked as Code and algorithm to check if a given short string is a substring of the main string. Can you get a linear solution (O(n)) if possible?

#### 17) How to return highest occurred character in a String? (solution)

You need to write a function to implement an algorithm which will accept a string of characters and should find the highest occurrence of the character and display it. For example if input is "aaaaaaaaaaaaaaaaabbbbcddddeeeeee" it should return "a".

#### 18) Write a program to remove a given character from String? (solution)

One of my favorite coding question, when I interview Java developers. You need to write a Java method which will accept a String and a character to be removed and return a String, which doesn't has that character e.g remove(String word, char ch).

You need to provide both iterative and recursive solution of this method and also has to write JUnit tests to cover cases like null and empty String, input which only contains a letter to be removed, String which doesn't contain given character etc.

For more coding and algorithmic questions, you can also check the Cracking the Coding Interview 6th Edition book, which contains over 189 Programming Questions and Solutions.

#### 19) Write a program to find the longest palindrome in a string? (solution)

This is one of the tough coding question based upon String. It's hard to think about an algorithm to solve this problem until you have practiced well. What makes it more difficult is the constraint that your solution has O(n) time complexity and O(1) space complexity.

#### 20) How to sort String on their length in Java? (solution)

Write a Program to sort String on their length in Java? Your method should accept an array of String and return a sorted array based upon the length of String. Don't forget to write unit tests for your solution.

That's all on this list of 15 String Algorithm based coding questions. These are a really good question to prepare for programming job interviews, not only you can expect the same question on a real interview but also it will prepare you how to tackle algorithmic coding interview questions. Even if you don't find the same question, you would be able to apply the knowledge you gain by solving these question by yourself.

Always remember, you are judged by the code you write, so always write production quality code, which would pass the general test, corner cases, invalid inputs, robustness test and also pass the performance test.  Whenever asked to solve a coding problem, always think about all possible input and write a test for that.

Further Learning
Data Structures and Algorithms: Deep Dive Using Java
Algorithms and Data Structures - Part 1 and 2
Cracking the Coding Interview - 189 Questions and Solutions

Related Data Structure and Algorithm Interview Questions from Javarevisited Blog
• Top 15 Data Structure and Algorithm Interview Questions (see here)
• Top 30 Array-based coding interview questions (see here)
• 133 core Java interview questions of the last 5 years (see here)
• Top 30 linked list coding interview questions (see here)
• Top 50 Java Programs from Coding Interviews (see here)
• Top 5 books on Programming/Coding Interviews (list)
• 100+ Data Structure Coding Problems from Interviews (questions)
• 10 Free Data Structure and Algorithm Courses for Programmers (courses)
• How to convert a linked list to an array in Java? (example)
• How to find a missing value from an array containing 1 to 100? (solution)
• How to reverse an array in place in Java? (solution)
• My favorite free courses to learn data Structure in depth (FreeCodeCamp)
• Top 5 Books to Learn Data Structure and Algorithms (books)
• How to count the number of leaf nodes in a given binary tree in Java? (solution)
• How to remove duplicates from an array in Java? (solution)
• 50+ Data Structure and Algorithms Problems from Interviews (questions)
• Iterative PreOrder traversal in a binary tree (solution)
• Recursive InOrder traversal Algorithm (solution)
• 10 Algorithms Courses to Crack Programming Job Interviews (courses)
Thanks for reading this article so far. If you like these questions then please share with your friends and colleagues. If you have any other interesting question which you have faced on interviews, drop us a note.

P. S. - If you are looking for some Free Algorithms courses to improve your understanding of Data Structure and Algorithms, then you should also check the Easy to Advanced Data Structures course on Udemy. It's authored by a Google Software Engineer and Algorithm expert and its completely free of cost.

Anonymous said...

Can you also add some puzzles based on parent-child or recursion.

Anonymous said...

What language would you advise as a monthly typed language?

Anonymous said...

15) How to check if a String is valid shuffle of two String?

static boolean isShuffle(String A, String B, String C) {
char[] aChar = A.toCharArray();
char[] bChar = B.toCharArray();
char[] cChar = C.toCharArray();

int aIndex=0, bIndex=0;
for (int i = 0; i < cChar.length; i++) {
if ((aIndex < aChar.length) && (cChar[i] == aChar[aIndex])) {
aIndex++;
} else if ((bIndex < bChar.length) && (cChar[i] == bChar[bIndex])) {
bIndex++;
} else
return false;
}

return true;
}

Anonymous said...

16) Write a program to check if a String contains another String e.g. indexOf()

static public int indexOf(String word, String subWord) {
char[] wordChar = word.toCharArray();
char[] subChar = subWord.toCharArray();

int subCharIndex = 0;
for (int j = 0; j < wordChar.length; j++) {
if ((subCharIndex < subChar.length) && (wordChar[j] == subChar[subCharIndex])) {
subCharIndex++;
if (subCharIndex == subChar.length)
return j - subChar.length + 1;
} else
subCharIndex = 0; // reset it
}

return -1;
}

Anonymous said...

17) How to return highest occurred character in a String?

static public char highest(String word) {
int highestCount = 0;
char highestChar = ' ';
char[] wordChar = word.toLowerCase().toCharArray();
int asciiOffset = 97; // 65 for upper-case
int[] counter = new int[26]; // number of letters

for (int i = 0; i < wordChar.length; i++) {
counter[wordChar[i] - asciiOffset] ++;
if (counter[wordChar[i] - asciiOffset] > highestCount) {
highestCount = counter[wordChar[i] - asciiOffset];
highestChar = wordChar[i];
}
}

return highestChar;
}

Anonymous said...

18) Write a program to remove a given characters from String

So, without detailed error checking and JUnit tests, here is my solution:
public static String remove(String word, char ch) {
if (word == null)
return "WARNING: null string !";
if (word.length() == 0)
return "WARNING: empty string !";

char[] wordChar = word.toCharArray();
char[] toReturn = new char[wordChar.length];
int toReturnLength = 0;
for (int i = 0; i < wordChar.length; i++) {
if (wordChar[i] != ch) {
toReturn[toReturnLength++] = wordChar[i];
}
}

return String.valueOf(toReturn).trim();
}

public static String removeRecursive(String word, char ch) {
if (word == null)
return "WARNING: null string !";
if (word.length() == 0)
return "WARNING: empty string !";

char[] wordChar = word.toCharArray();
char[] tempWord = new char[wordChar.length];
int iTemp = 0;

for (int i = 0; i < wordChar.length; i++) {
if (wordChar[i] == ch) {
String preString = String.valueOf(tempWord).trim();
StringBuilder sb = new StringBuilder();
for (int j = i+1; j < wordChar.length; j++) {
sb.append(wordChar[j]);
}
return removeRecursive(preString + sb.toString(), ch);
} else
tempWord[iTemp++] = wordChar[i];
}

return word;
}

Anonymous said...

13) How to check if String is Palindrome?

Multi-word, disregarding everything other than letters, at time complexity O(n)

public static boolean isLetter(char c) {
return ((c>=65 && c<=90) || (c>=97 && c<=122));
}

public static boolean isItPalindrome(String word) {
int indexRight = word.length() - 1;
for (int i = 0; i < word.length(); i++) {
if (isLetter(word.charAt(i))) {
if (isLetter(word.charAt(indexRight))) {
if (word.charAt(i) != word.charAt(indexRight)) {
return false;
}
}
indexRight--;
} // else nothing - go to next letter

if (i >= indexRight)
break;
}

return true;
}

Anonymous said...

I would really, really, like to see the solution of O(n) time complexity for:
19) Write a program to find longest palindrome in a string

Anonymous said...

19)longest palindrome in a string

import java.util.*;

public class longestpal
{
public static void main(String [] ass)
{
String as;
System.out.println("Enter a string to find longest palindrome");
Scanner scr=new Scanner(System.in);
as=scr.next();
int len=as.length();
int lng;
int index;
lng=0;
index=0;
for(int i=1;i-1&& i+jlng)
{lng=j;
index=i;
}
j++;

}

}
System.out.println(as.substring(index-lng,index+lng));
}
}

Gopi said...

Thank you @Anonymous for providing solution of unsolved problem.

Anonymous said...

Can anyone please provide solution to display all permutation of String without using recursion?

javin paul said...

@Anonymous, please see my solution here

Unknown said...

20) How to sort String on their length in Java? (solution)

I did it in C++

#include
#include
#include
#include
using namespace std;

struct strsize{
bool operator() (const string &lhs, const string &rhs) const{
return (lhs.length() > rhs.length());
}
};

int main()
{
set strset;
vector strvec = {{"afffbc"},{"abdfs"},{"sdhshsg"},{"sd"}};
cout << "Unordered string list "<<endl;
for(auto& it:strvec)
{
cout << it << endl;
strset.insert(it);
}
cout << "Ordered string list by size"<<endl;
for(auto& it:strset)
{
cout << it << endl;
}

}

Unknown said...

14) How to remove duplicate characters from String?

#include
#include
#include
#include
#include "string.h"
using namespace std;

int main()
{
char* str = "bananas";

string output;
set charmap;
for(int i=0; i<strlen(str);i++)
{
auto it = charmap.insert(str[i]);
if(it.second == true)
{
output.push_back(str[i]);
}
}

cout << output << endl;
}

Anonymous said...

How to remove duplicate characters from String? (solution)

private static void removeduplicates(String string) {
char[] chArray = string.toCharArray();
StringBuffer sb = new StringBuffer();
ArrayList list = new ArrayList();
for(char ch:chArray) {
if(list.contains(ch)) {
}else{
}
}
System.out.println(list);

for(int i=0; i< list.size(); i++) {
sb.append(list.get(i));
}
System.out.println(sb.toString());

}

Anonymous said...

Replace blank with "%20" solution
public class Replaceblank {
public static void main(String[] args){
System.out.println(replaceBlank("java is great"));
}
public static StringBuilder replaceBlank(String s){

StringBuilder str = new StringBuilder(s.replaceAll("\\s","%20"));
return str;
}
}

Unknown said...

This is my code
import java.util.*;
public class Friends
{
public static void main(String args[])
{
Scanner in=new Scanner(System.in);
String f_name[]=new String[5];
String l_name[]=new String[5];
String l_concat[]=new String[5];
int sr[]=new int[5];
int i;
System.out.print("\f");
for(i=0;i<3;i++)
{
sr[i]=in.nextInt();
f_name[i]=in.nextLine();
l_name[i]=in.nextLine();
}
for(i=0;i<3;i++)
{
System.out.println("sr "+i+" first name: "+l_name[i]+" last name: "+f_name[i]);
}
}

}

And in the output has both string msg of First name and Last name come together Please help me..........

Joe said...

My answer to question 20. Sort an array of String based on their length.
I did the sorting using bubble sort.

public static void main(String[] args) {
String[] arr = { "do", "the", "that", "I" };
sortArrayLength(arr);
}

private static void sortArrayLength(String[] arr) {
boolean flag = true;
while(flag){
flag = false;
for (int j = 0; j < arr.length-1; j++) {
if (arr[j].length() > arr[j + 1].length()) {
String temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
flag =true;
}
}
}
System.out.println("Sorted Array " + Arrays.toString(arr));
}

Unknown said...

"India is my country" =input
"andii5 si2 ym2 yountrc7"= output
Can anyone help me with this problem??

Unknown said...

"India is my country" =input
"andii5 si2 ym2 yountrc7"= output
Can anyone help me with this problem??

Mohd IShaque said...

public class JavaRevistedquestion {
public static void main(String[] args) {
String s="India is my country";
System.out.println(findLogic(s));
}

/*"India is my country" =input
"andii5 si2 ym2 yountrc7"= output */

public static String findLogic(String s){

if(s==null) {
return null;
}
String[] arr= s.split(" ");
String result="";
for(String st: arr){
result+=swapfirstAndLastChar(st.trim())+st.length()+" ";
}
return result;
}
public static String swapfirstAndLastChar(String s){
char[] charArr=s.toCharArray();
char temp=charArr[0];
charArr[0]=charArr[s.length()-1];
charArr[s.length()-1]=temp;
return new String(charArr);

}
}

Unknown said...

15)

public static boolean validShuffle(String one, String two, String three) {
char[] oneArray = one.toCharArray();
char[] twoArray = two.toCharArray();

for (int i = oneArray.length-1; i>0; i--) {
if(three.indexOf(oneArray[i]) < three.indexOf(oneArray[i-1])) {
return false;
}
}

for (int i = twoArray.length-1; i>0; i--) {
if(three.indexOf(twoArray[i]) < three.indexOf(twoArray[i-1])) {
return false;
}
}

return true;
}

Unknown said...

14) Remove duplicate characters from a string while maintaining order (must use LinkedHashMap.

public static String removeDuplicateChar(String input) {
System.out.println("Removing duplicate characters in String: \"" + input + "\"...");

for(int i = 0; i e : charMap.entrySet()) {
if(e.getValue() == 1)
sb.append(e.getKey());
}

System.out.println(sb.toString());
return sb.toString();
}

Unknown said...

19)

/*finds two letters at a time and the index of the end of the reverse of those two letters
*creates a substring of the start and end of those indexs and determines if that is palendrome
*through stringbuilder reverse function. if it is a palendrome and length is longer than current..found new longest
*/
public static void findLongestPalendrome(String input) {
System.out.println("Finding longest palendrome in string: \"" + input + "\"...");
String longestPalendrom = "";
for(int i = 0; i<input.length()-1; i++) {
StringBuilder sb = new StringBuilder(input.substring(i, i+2));
sb.reverse();
if(input.contains(sb)) {
int endPalendromeIndex = input.substring(i).indexOf(sb.toString())+1+i;
StringBuilder isPalendrome = new StringBuilder(input.substring(i, endPalendromeIndex+1));
if(isPalendrome.toString().equals(isPalendrome.reverse().toString()) &&
longestPalendrom.length() < isPalendrome.length()) {
longestPalendrom = isPalendrome.toString();
}
}
}
System.out.println("Found longest palendrome to be: " + longestPalendrom);
}

Unknown said...

20). you can use Comparator to define your own sorting order

public static void sortBasedOnStrLength(String[] strArray) {
List list = Arrays.asList(strArray);

Collections.sort(list, new Comparator() {
public int compare(String o1, String o2) {
return o1.length() - o2.length();
}
});
System.out.println("Sorted list is:" + list);
}

Unknown said...

common elements from two strings.

import java.util.HashSet;

public class CommonString {

public static void main(String[] args) {

String s1[]={"one","two","three","four","five","four"};
String s2[]={"seven","two","eight","four","nine","four"};
HashSet hs = new HashSet();

for(int i=0;i<s1.length;i++)
{
for(int j=0;j<s1.length;j++)
{
if(s1[i]==(s2[j]))
{
}
}
}

System.out.println(hs);

}
}

Unknown said...

How to return highest occurred character in a String using hashmap

import java.util.HashMap;
import java.util.Map;

public class MaxOccuringChar {

public static void main(String[] args) {

String s1="aaaaaaaa aaaa bbbbbb cccc dddd";
int maxoc=0;
HashMap hm= new HashMap();
for(char c:s1.toCharArray())
{
if(c==' ')
continue;
if(hm.containsKey(c))
hm.put(c, hm.get(c)+1);
else
hm.put(c, 1);
if(hm.get(c)>maxoc)
maxoc=hm.get(c);
}

for(Map.Entry entry:hm.entrySet())
{
if(entry.getValue()==maxoc)
{
System.out.println(entry.getKey()+" "+maxoc);
}
}
}

}

Unknown said...

Problem:1)
Input:a6c5b3a3d7b2
Output:a9b5c5d7

Unknown said...

'the Army' and 'Mary' are not anagrams. 'Mary' doesn't have a 't', 'h', or 'e'

Unknown said...

write pseudo code to print the words followed by vowels(a,e,i,o,u) in the word, only if the word have 't' occurring in them?

1example:all the best

output: the(1)

best(1)

2example: touch the thunder

output: touch(2)

the(1)

thunder(2)

3example: all is well

output: (0)

it must contain 't' with vowels in word. even it contain vowels if 't' not there i won't consider.

Unknown said...

import java.util.*;

public class HighestOccurenceCharacter
{
public static void main(String arg[])
{
System.out.println("enter the string ");
Scanner sc=new Scanner(System.in);
String str=sc.nextLine();

int arr[]=new int[256];

for(int i=0;i<256;i++)
{
arr[i]=0;
}

for(int i=0;i<str.length();i++)
{
arr[str.charAt(i)]++;
}

int max=0;
int latter=0;
for(int i=0;i<256;i++)
{
if(max<arr[i])
{
max=arr[i];
latter=i;
}
}
System.out.printf("character is= %c\n",latter);
System.out.println("count is="+max);

}
}