String Based Programs : Good to practice before an interview

Program 1: Print duplicate characters from String Using Java ?

public class Nishant001 
{
/*
Typically, ASCII characters are 256, so we use our Hash array size as 256.
*/
    static final int NO_OF_CHARS = 256;
     
    /* Fills count array with frequency of characters */
    static void fillCharCounts(String str, int[] count)
    {
       for (int i = 0; i < str.length();  i++)
          count[str.charAt(i)]++;
    }
     
    /* Print duplicates present in the passed string */
    static void printDups(String str)
    {
      // Create an array of size 256 and fill count of every character in it
      int count[] = new int[NO_OF_CHARS];
      fillCharCounts(str, count);
     
      for (int i = 0; i < NO_OF_CHARS; i++)
        if(count[i] > 1)
            System.out.printf("%c,  count = %d \n", i,  count[i]);
     
    }
     
    // Driver Method
    public static void main(String[] args)
    {
        String str = "test string";
        printDups(str);
    }
}

Output:

s,  count = 2
t,  count = 3

Time Complexity : O(n)


Program 2: Print maximum occurring character in an input string

// Java program to output the maximum occurring character
// in a string
/*
Typically, ASCII characters are 256, so we use our Hash array size as 256.
But if we know that our input string will have characters with value from 0 to 127 only,
we can limit Hash array size as 128. Similarly, based on extra info known about input string,
the Hash array size can be limited to 26.
*/
 
public class Nishant002
{
    static final int ASCII_SIZE = 256;
    static char getMaxOccuringChar(String str)
    {
        // Create array to keep the count of individual
        // characters and initialize the array as 0
        int count[] = new int[ASCII_SIZE];
     
        // Construct character count array from the input
        // string.
        int len = str.length();
        for (int i=0; i<len; i++)
            count[str.charAt(i)]++;
     
        int max = -1;  // Initialize max count
        char result = ' ';   // Initialize result
     
        // Traversing through the string and maintaining
        // the count of each character
        for (int i = 0; i < len; i++) {
            if (max < count[str.charAt(i)]) {
                max = count[str.charAt(i)];
                result = str.charAt(i);
            }
        }
     
        return result;
    }
     
    // Driver Method
    public static void main(String[] args)
    {
        String str = "sample string";
        System.out.println("Max occurring character is " +
                            getMaxOccuringChar(str));
    }
}


output:

Max occurring character is s

Time Complexity: O(n)
Space Complexity: O(1) — Because we are using fixed space (Hash array) irrespective of input string size.


Program 3: Remove duplicates from a given string


import java.util.Arrays;
public class Nishant003
{
    /* Method to remove duplicates in a sorted array */
    static String removeDupsSorted(String str)
    {
        int res_ind = 1, ip_ind = 1;
         
        // Character array for removal of duplicate characters
        char arr[] = str.toCharArray();
         
        /* In place removal of duplicate characters*/
        while (ip_ind != arr.length)
        {
            if(arr[ip_ind] != arr[ip_ind-1])
            {
                arr[res_ind] = arr[ip_ind];
                res_ind++;
            }
            ip_ind++;
           
        }
     
        str = new String(arr);
        return str.substring(0,res_ind);
    }
     
    /* Method removes duplicate characters from the string
       This function work in-place and fills null characters
       in the extra space left */
    static String removeDups(String str)
    {
       // Sort the character array
       char temp[] = str.toCharArray();
       Arrays.sort(temp);
       str = new String(temp);
       
       // Remove duplicates from sorted
       return removeDupsSorted(str);
    }
     
    // Driver Method
    public static void main(String[] args)
    {
        String str = "nishantsharma";
        System.out.println(removeDups(str));
    }
}

output:

nishatrm

Time Complexity: O(n log n) If we use some nlogn sorting algorithm instead of quicksort.

// Java prigram to remove duplicates
import java.util.*;
 
class RemoveDuplicates
{
    /* Function removes duplicate characters from the string
    This function work in-place */
    void removeDuplicates(String str)
    {
        LinkedHashSet<Character> lhs = new LinkedHashSet<>();
        for(int i=0;i<str.length();i++)
            lhs.add(str.charAt(i));
         
        // print string after deleting duplicate elements
        for(Character ch : lhs)
            System.out.print(ch);
    }
     
    /* Driver program to test removeDuplicates */
    public static void main(String args[])
    {
        String str = "nishantsharma";
        RemoveDuplicates r = new RemoveDuplicates();
        r.removeDuplicates(str);
    }
}

output:

nishatrm

Time Complexity: O(n)


Program 4: Program to check if input is an integer or a string


import java.io.*;
public class Nishant004{

// Returns true if s is
// a number else false
static boolean isNumber(String s)
{
for (int i = 0; i < s.length(); i++)
if (Character.isDigit(s.charAt(i))
== false)
return false;

return true;
}

// Driver code
static public void main (String[] args)
{
// Saving the input in a string
String str = "6790";

// Function returns 1 if all elements
// are in range '0 - 9'
if (isNumber(str))
System.out.println("Integer");

// Function returns 0 if the
// input is not an integer
else
System.out.println("String");

}
}


Program 5: Print all the duplicates in the input string

// Java program to count all duplicates from string using hashing

public class Nishant005
{
static final int NO_OF_CHARS = 256;

/* Fills count array with frequency of characters */
static void fillCharCounts(String str, int[] count)
{
for (int i = 0; i < str.length(); i++)
count[str.charAt(i)]++;
}

/* Print duplicates present in the passed string */
static void printDups(String str)
{
// Create an array of size 256 and fill count of every character in it
int count[] = new int[NO_OF_CHARS];
fillCharCounts(str, count);

for (int i = 0; i < NO_OF_CHARS; i++)
if(count[i] > 1)
System.out.printf("%c, count = %d \n", i, count[i]);

}

// Driver Method
public static void main(String[] args)
{
String str = "test string";
printDups(str);
}
}


Program 6: Write a program to print all permutations of a given string

public class Nishant006
{
public static void main(String[] args)
{
String str = "ABC";
int n = str.length();
Nishant006 permutation = new Nishant006();
permutation.permute(str, 0, n-1);
}

/**
* permutation function
* @param str string to calculate permutation for
* @param l starting index
* @param r end index
*/
private void permute(String str, int l, int r)
{
if (l == r)
System.out.println(str);
else
{
for (int i = l; i <= r; i++)
{
str = swap(str,l,i);
permute(str, l+1, r);
str = swap(str,l,i);
}
}
}

/**
* Swap Characters at position
* @param a string value
* @param i position 1
* @param j position 2
* @return swapped string
*/
public String swap(String a, int i, int j)
{
char temp;
char[] charArray = a.toCharArray();
temp = charArray[i] ;
charArray[i] = charArray[j];
charArray[j] = temp;
return String.valueOf(charArray);
}

}

Output:

ABC
ACB
BAC
BCA
CBA
CAB


Program 007: Write a program to check whether two strings are anagram of each other.

/*
An anagram of a string is another string that contains same characters, only the order of characters can be different.
For example, “abcd” and “dabc” are anagram of each other.
*/

// JAVA program to check whether two strings
// are anagrams of each other
import java.io.*;
import java.util.Arrays;
import java.util.Collections;

class Nishant007 {

/* function to check whether two strings are
anagram of each other */
static boolean areAnagram(char[] str1, char[] str2)
{
// Get lenghts of both strings
int n1 = str1.length;
int n2 = str2.length;

// If length of both strings is not same,
// then they cannot be anagram
if (n1 != n2)
return false;

// Sort both strings
Arrays.sort(str1);
Arrays.sort(str2);

// Compare sorted strings
for (int i = 0; i < n1; i++)
if (str1[i] != str2[i])
return false;

return true;
}

/* Driver program to test to print printDups*/
public static void main(String args[])
{
char str1[] = { 't', 'e', 's', 't' };
char str2[] = { 't', 't', 'e', 'w' };
if (areAnagram(str1, str2))
System.out.println("The two strings are"
+ " anagram of each other");
else
System.out.println("The two strings are not"
+ " anagram of each other");
}
}

Output:  The two strings are not anagram of each other