Learn Automation Testing Easily and become skilled Automation Tester
Pages
▼
Java String Programs
String Programs:
1)String Methods Demo Program
package stringhandling;
public class StringAPIDemo {
public static void main(String[] args) { //declaring String literal object String s="java"; // 0123 //1.length()-->number of characters in the String return type int int cnt=s.length(); System.out.println("number of character in string is-->"+cnt); //2.charAt(int index)-->returns a char at given index
char c=s.charAt(2);
System.out.println("character at 2nd index in given string is-->"+c);
//3.toCharArray()-->convert the given string into char[]
System.out.println("*************************");
System.out.println("for each loop");
for(char c1:ch) { System.out.print(c1+"\t");
}
System.out.println();
//4. concat(String str):joins the given two strings..returns String object
String s2=s.concat("selenium");
System.out.println("s2 value using concat() is-->"+s2);
//toUpperCase()-->converts the string into UpperCase letters returns String
String s3=s2.toUpperCase();
System.out.println("s3 value using toUpperCase() is-->"+s3);
//toLowerCase(): converts the String into lowerCase returns String
String s4=s3.toLowerCase();
System.out.println("s4 value toLowerCase() is-->"+s4);
//boolean methods
//isEmpty()-->given string is empty or not returns true else false
boolean b=s.isEmpty();
System.out.println("checking whether "+s+" isempty or not:"+b);
//contains(String str): checks whether givne string is present in another string or not returns boolean
boolean b1=s2.contains(s);
System.out.println("checking "+s+" is present in "+s2+" using contains(): "+b1);
boolean b2=s2.contains("ruby");
System.out.println("checking ruby is present in "+s2+" using contains(): "+b2);
//equals(Object obj):compares two given strings
boolean b3=s2.equals(s3);
System.out.println("comparing "+s2+" with "+s3+" using equals() b3: "+b3);
boolean b4=s2.equals(s4); System.out.println("comparing "+s2+" with "+s4+" using equals() b4: "+b4); //equalsIgnoreCase():compares both the strings and ignores the cases returns boolean value boolean b5=s2.equalsIgnoreCase(s3); System.out.println("comparing "+s2+" with "+s3+" using equalsIgnoreCase() b5: "+b5); //startsWith(String str):checks given string is starting with the other string or not boolean b6=s2.startsWith(s); System.out.println("checking s2: "+s2+" is starting with s:"+s+" using startsWith() b6:"+b6); boolean b7=s2.startsWith("selenium"); System.out.println("checking s2: "+s2+" is starting with selenium using startsWith() b7:"+b7); //endsWith():checks the String is ending with given string or not boolean b8=s2.endsWith("selenium"); System.out.println("checking s2:"+s2+" ending with selenium using endsWith() b8: "+b8); boolean b9=s2.endsWith("ruby"); System.out.println("checking s2:"+s2+" ending with ruby using endsWith() b9: "+b9); //subString:portion of string is called subString //subString(int beginindex): it fetches all the characters from begin index to last returns String //subString(int beginindex,int endindex): String s1="Learn Automation"; //index 0123456789101112131415 String s5=s1.substring(6); System.out.println("fetching automation from "+s1+" using subString(int index) s5:"+s5); String s6=s1.substring(0, 5); System.out.println("fetching learn from :"+s1+" using subString(int b,int e) s6:"+s6); //split("delimiter"):splits the given string based on given delimiter and store in String[] //delimiter : space , . " ' ? String s7="About 4,05,00,000 results (0.45 seconds)"; String[] str=s7.split(" "); //str[]=["About","4,05,00,000","results","(0.45","seconds)"] // 0 1 2 3 4 String s8=str[1]; System.out.println("s8 value is--:"+s8); //replaceAll(): replaces the given string/char in all the places of String String s9=s8.replaceAll(",", ""); System.out.println("s9 value using replaceAll()-->"+s9); //replace(oldchar/String, replace char/String):replaces the old char/String with new char/String String s10=s1.replace('a', '@'); System.out.println("s10 value suing replace():"+s10); String s11=s2.replace("java", "python"); System.out.println(s2+ " is replaced with pythoin uisng replace():"+s11); //indexOf(char c/String): finds the index of given char/String returns int value int indx=s2.indexOf('a'); System.out.println("finds the a character index in:"+s2+" usinf indexOf() -->"+indx); int indx2=s2.indexOf("selenium"); System.out.println("finds the selenium index in:"+s2+" usinf indexOf() -->"+indx2); //lastIndexOf():finds the last index of the character int lindx=s1.lastIndexOf('a'); System.out.println("last index of a character in:"+s1+" uisnf lastIndex():"+lindx); //getBytes() : it returns byte[] byte[] bt=s.getBytes(); for(byte t:bt) { System.out.print(t+"\t"); } System.out.println(); //compareTo(): int i1=s2.compareTo(s3); System.out.println("comparing s2 :"+s2+" with s3: "+s3+" using compareTo() -->"+i1); int i2=s2.compareTo(s4); System.out.println("comparing s2 :"+s2+" with s4: "+s4+" using compareTo() -->"+i2); int i3=s3.compareTo(s2); System.out.println("comparing s3 :"+s3+" with s2: "+s2+" using compareTo() -->"+i3); //you can find the length of a String without length() int i4=s.compareTo(""); System.out.println("length of s :"+s+" is : "+i4); //join(delimiter,"str1","str2","str3"):joins the given delimiter inbetween all the strings return new string String s13=String.join("-", "2020","April","21"); System.out.println("s13 value is-->"+s13); //valueOf():converts the givne object into String format int i=25; String s14=String.valueOf(i); String s15=s14+i; //"25"+25 System.out.println("s14+i output is-->"+s15); }
}
===========================================
2. Check Given String is palindrome or not?
public static void checkPalindrome(String str) {
//1.convert the given string into lowercase
str=str.toLowerCase();
//2. declare flag as true kayak
boolean flag=true;
//3.iterate the string inforward and backward then compare from begining and end characters till middle of the string is reached
for(int i=0;i<str.length()/2;i++) {
if(str.charAt(i)!=str.charAt(str.length()-i-1)) {
//set the flag as false
flag=false;
break;
}
}
if(flag) {
System.out.println("given "+str+" is palindrome");
}else {
System.out.println("given "+str+" is not palindrome");
}
}
=============================================
3. findout the Vowels & Consonants count in Given String
static void countVowelsAndConsonants(String str) { //declare vowels and consonant count variables int vCount=0,cCount=0; //convert the String into lowercase str=str.toLowerCase(); //iterate the String using for loop for(int i=0;i<str.length();i++) { if(str.charAt(i)=='a'||str.charAt(i)=='e'||str.charAt(i)=='i'||str.charAt(i)=='o'||str.charAt(i)=='u') { //increment vCount by 1 vCount++; }else { //increment consonant count by 1 cCount++; } } System.out.println("Number of vowels in given string is-->"+vCount); System.out.println("Number of Consonants in given string is-->"+cCount); }
=========================================
4. Check given two Strings are anagrams or not?
Two Strings are called the anagram if they contain the same characters. However, the order or sequence of the characters can be different.
protected static void checkAnagrams(String str1,String str2) { //converts the Strings into lowercase str1=str1.toLowerCase(); str2=str2.toLowerCase(); //check the lengths of both the strings if(str1.length()!=str2.length()) { System.out.println("both strings are not anagrams"); }else { //convert the String into char[] format using toCharArray(); char[] str1Array=str1.toCharArray(); char[] str2Array=str2.toCharArray(); //sort the array using Arrays class sort(); Arrays.sort(str1Array); Arrays.sort(str2Array); //comparing both the arrays using equals() of Arrays class if(Arrays.equals(str1Array, str2Array)==true) { System.out.println("Given Strings are anagrams"); }else { System.out.println("both strings are not anagrams"); } } }
==========================================
5. StringBuffer Methods Demo:
package stringhandling;
public class StringBufferDemo {
public static void main(String[] args) { //Create object for StringBuffer class StringBuffer sb=new StringBuffer("java");
System.out.println("sb value is-->"+sb); //append()-->append the givne string with exisitng string
sb.append("webdriver");
System.out.println("sb value after append() is-->"+sb);
//insert(int index,String str): it insert the given string at index specified
//java webdriver
//012345678910111213
sb.insert(4, " ");
System.out.println("sb value after insert() is-->"+sb);
//repalce(int i1,int i2,string replacement);
sb.replace(0, 4, "python");
System.out.println("sb value after replace() is-->"+sb);
//delete(4,14):deletes the characters in given range
sb.delete(6,16);
System.out.println("sb value after delete() is-->"+sb);
//reverse():reverse the given string
sb.reverse();
System.out.println("sb value after reverse() is-->"+sb);
}
}
============================================== Write a java program to count the total number of occurrences of a given character in a string without using any loop?
public class CountCharacterOccurence
{
public static void main(String[] args)
{
String s = "Java is java again java again";
char c = 'a';
int count = s.length() - s.replace("a", "").length();
System.out.println("Number of occurances of 'a' in "+s+" = "+count);
}
}
==============================================
Write a java program to count the number of words in a string?
class CountTheWords
{
public static void main(String[] args)
{
System.out.println("Enter the string");
Scanner sc = new Scanner(System.in);
String s=sc.nextLine();
String[] words = s.trim().split(" ");
System.out.println("Number of words in the string = "+words.length);
}
}
----------------------------------------------------------------
public class CountTheWordsInGivenString
{
public static void main(String[] args)
{
System.out.println("Enter the string");
Scanner sc = new Scanner(System.in);
String s=sc.nextLine();
int count = 1;
for (int i = 0; i < s.length()-1; i++)
{
if((s.charAt(i) == ' ') && (s.charAt(i+1) != ' '))
{
count++;
}
}
System.out.println("Number of words in a string = "+count);
}
}
==================================================================
How To Remove White Spaces From String In Java Using Built-In Methods?
we use replaceAll() method of String class to remove all white spaces (including tab also) from a string. This is one of the easiest method to remove spaces from string in java. replaceAll() method takes two parameters. One is the string to be replaced and another one is the string to be replaced with.
import java.util.Scanner;
public class RemoveWhiteSpaces
{
public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
System.out.println("Enter input string to be cleaned from white spaces...!");
How To Remove White Spaces From String Without Using Built-In Methods?
first we convert the given input string to char array and then we traverse this array to find white spaces. We concatenate the characters which are not the white spaces to String object.
import java.util.Scanner;
public class RemoveWhiteSpaces
{
public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
System.out.println("Enter input string to be cleaned from white spaces...!");
String inputString = sc.nextLine();
char[] charArray = inputString.toCharArray();
String stringWithoutSpaces = "";
for (int i = 0; i < charArray.length; i++)
{
if ( (charArray[i] != ' ') && (charArray[i] != '\t') )
{
stringWithoutSpaces = stringWithoutSpaces + charArray[i];
}
}
System.out.println("Input String Without Spaces : "+stringWithoutSpaces);
sc.close();
}
}
============================================================
How To Swap Two String Variables Without Using Third OR Temp Variable In Java
To swap two string variables without using third or temp variable, we use substring() method of String class. This method has two overloaded forms.
1) substring(int beginIndex)
It returns substring of a calling string starting with the character at the specified index and ending with the last character of the calling string.
2) substring(int beginIndex, int endIndex)
It returns substring of a calling string starting with the character at beginIndex (inclusive) and ending with the character at endIndex (exclusive).
import java.util.Scanner;
public class SwapTwoStrings
{
public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
System.out.println("Enter First String :");
String s1 = sc.next();
System.out.println("Enter Second String :");
String s2 = sc.next();
System.out.println("Before Swapping :");
System.out.println("s1 : "+s1);
System.out.println("s2 : "+s2);
//Swapping starts
s1 = s1 + s2;
s2 = s1.substring(0, s1.length()-s2.length());
s1 = s1.substring(s2.length());
//Swapping ends
System.out.println("After Swapping :");
System.out.println("s1 : "+s1);
System.out.println("s2 : "+s2);
}
}
==========================================================
How To Reverse The String With Preserving The Position Of Spaces?
public class MainClass
{
static void reverseString(String inputString)
{
//Converting inputString to char array 'inputStringArray'
//Defining a new char array 'resultArray' with same size as inputStringArray
char[] resultArray = new char[inputStringArray.length];
//First for loop :
//For every space in the 'inputStringArray',
//we insert spaces in the 'resultArray' at the corresponding positions
for (int i = 0; i < inputStringArray.length; i++)
{
if (inputStringArray[i] == ' ')
{
resultArray[i] = ' ';
}
}
//Initializing 'j' with length of resultArray
int j = resultArray.length-1;
//Second for loop :
//we copy every non-space character of inputStringArray
//from first to last at 'j' position of resultArray
for (int i = 0; i < inputStringArray.length; i++)
{
if (inputStringArray[i] != ' ')
{
//If resultArray already has space at index j then decrementing 'j'
/ Java program to reverse a string using recursion
classStringReverse
{
/* Function to print reverse of the passed string */
voidreverse(String str)
{
if((str==null)||(str.length() <= 1))
System.out.println(str);
else
{
System.out.print(str.charAt(str.length()-1));
reverse(str.substring(0,str.length()-1));
}
}
/* Driver program to test above function */
publicstaticvoidmain(String[] args)
{
String str = "WebDriver";
StringReverse obj = newStringReverse();
obj.reverse(str);
}
}
=============================================================
Check Whether One String Is Rotation Of Another?
If s1 and s2 are two given strings, then write a java program to check whether s2 is a rotated version of s1?
Examples :
If “JavaJ2eeStrutsHibernate” is a string then below are some rotated versions of this string.
Step 1 : Check whether s1 and s2 are of same length. If they are not of same length then s2 is not rotated version of s1.
Step 2 : s3 = s1 + s1;
If s1 = “JavaJ2eeStrutsHibernate” then s3 = “JavaJ2eeStrutsHibernateJavaJ2eeStrutsHibernate”.
Step 3 : Check whether s3 contains s2 using contains() method of String class. If it contains then s2 is rotated version of s1.
public class StringRotation
{
public static void main(String[] args)
{
String s1 = "JavaJ2eeStrutsHibernate";
String s2 = "StrutsHibernateJavaJ2ee";
//Step 1
if(s1.length() != s2.length())
{
System.out.println("s2 is not rotated version of s1");
}
else
{
//Step 2
String s3 = s1 + s1;
//Step 3
if(s3.contains(s2))
{
System.out.println("s2 is a rotated version of s1");
}
else
{
System.out.println("s2 is not rotated version of s1");
}
}
}
}
=============================================
How To Find Longest Substring Without Repeating Characters In Java?
Step 1 : Convert the given inputString to an array of characters called charArray.
char[] charArray = inputString.toCharArray();
Step 2 : Initialize longestSubstring to null and longestSubstringLength to 0.
String longestSubstring = null;
int longestSubstringLength = 0;
Step 3 : Define one LinkedHashMap called charPosMap. It will hold characters of inputString as keys and their position as values. Here, we have used LinkedHashMap instead of HashMap because it maintains the insertion order of elements.
LinkedHashMap<Character, Integer> charPosMap = new LinkedHashMap<Character, Integer>();
Step 4 : For every char ch in charArray, check whether it is already present in charPosMap. If it is not present, add this char to charPosMap along with its position.
Step 5 : If char ch is present in charPosMap, reposition the cursor i to the position of ch and clear the charPosMap.
i = charPosMap.get(ch);
charPosMap.clear();
Step 6 : Check whether the size of charPosMap is greater than longestSubstringLength. If it is greater than longestSubstringLength, assign the size of charPosMap to longestSubstringLength and its keySet to longestSubstring.
How To Find All Permutations Of String In Java?
Problem :
Write a java program to find all permutations of string recursively. For example, all permutations of string “JSP” are,
JSP,JPS,SJP,SPJ,PJS,PSJ
public class PermutationsOfString
{
static public void StringPermutation(String input)
{
StringPermutation("", input);
}
public static void main(String[] args)
{
StringPermutation("JSP");
}
}
==========================================================
How To Find First Repeated And Non-Repeated Character In A String?
Step 1 : Define one HashMap called charCountMap with Character as key and Integer as value. This map will hold the characters and their count in the given string.
Step 2 : Convert inputString to char array called strArray.
Step 3 : Iterate through all chars of strArray and update their occurrences in charCountMap.
Step 4 : Iterate through all chars of strArray and check their count in charCountMap. Any first occurring character with 1 as it’s count will be the first non-repeated character in inputString.
Step 5 : Iterate through all chars of strArray and check their count in charCountMap. Any first occurring character with >1 as it’s count will be the first repeated character in inputString.
public class MainClass
{
static void firstRepeatedNonRepeatedChar(String inputString)
{
//Creating a HashMap containing char as a key and occurrences as a value
HashMap<Character, Integer> charCountMap = new HashMap<Character, Integer>();
//Converting inputString to char array
char[] strArray = inputString.toCharArray();
//Checking each char of strArray
for (char c : strArray)
{
if(charCountMap.containsKey(c))
{
//If char is present in charCountMap, incrementing it's count by 1
charCountMap.put(c, charCountMap.get(c)+1);
}
else
{
//If char is not present in charCountMap,
//adding this char in charCountMap with 1 as it's value
charCountMap.put(c, 1);
}
}
//checking for first non-repeated character
for (char c : strArray)
{
if (charCountMap.get(c) == 1)
{
System.out.println("First Non-Repeated Character In '"+inputString+"' is '"+c+"'");
break;
}
}
//checking for first repeated character
for (char c : strArray)
{
if (charCountMap.get(c) > 1)
{
System.out.println("First Repeated Character In '"+inputString+"' is '"+c+"'");
break;
}
}
}
public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
System.out.println("Enter the string :");
String input = sc.next();
firstRepeatedNonRepeatedChar(input);
}
}
==========================================================
How To Count Occurrences Of Each Character In String In Java?
you have to count the number of occurrences of each character in it. For example, If “Java J2EE Java JSP J2EE” is the given string then occurrences of each character in this string is E=4, 2=2, v=2, =4, P=1, S=1, a=4, J=5.
To find the number of occurrences of each character in a given string, we have used HashMap with character as a key and it’s occurrences as a value. First, we convert the given string to char array and check each character one by one. And update it’s count in HashMap
import java.util.HashMap;
public class EachCharCountInString
{
private static void characterCount(String inputString)
{
//Creating a HashMap containing char as a key and occurrences as a value
HashMap<Character, Integer> charCountMap = new HashMap<Character, Integer>();
//Converting given string to char array
char[] strArray = inputString.toCharArray();
//checking each char of strArray
for (char c : strArray)
{
if(charCountMap.containsKey(c))
{
//If char 'c' is present in charCountMap, incrementing it's count by 1
charCountMap.put(c, charCountMap.get(c)+1);
}
else
{
//If char 'c' is not present in charCountMap,
//putting 'c' into charCountMap with 1 as it's value
characterCount("Done And Gone");
}
}
===========================================================
How To Reverse Each Word Of A String In Java?
public class ReverseEachWord
{
static void reverseEachWordOfString(String inputString)
{
String[] words = inputString.split(" ");
String reverseString = "";
for (int i = 0; i < words.length; i++)
{
String word = words[i];
reverseEachWordOfString("I am string not reversed");
reverseEachWordOfString("Reverse Me");
}
}
=============================================================
Print All Substrings Of A String In Java
a) Using substring() method :
In this method, we find substring between every ith character and subsequent characters i.e from i+1 to inputString.length().
for (int i = 0; i < inputString.length(); i++)
{
for (int j = i+1; j <= inputString.length(); j++)
{
System.out.println(inputString.substring(i, j));
}
}
b) Using StringBuilder
In this method, we go on appending subsequent characters with every ith character using StringBuilder.
for (int i = 0; i < inputString.length(); i++)
{
subSring = new StringBuilder().append(inputString.charAt(i));
System.out.println(subSring);
for (int j = i+1; j < inputString.length(); j++)
{
subSring.append(inputString.charAt(j));
System.out.println(subSring);
}
}
=======================================
How To Find Duplicate Characters In A String In Java?
We use HashMap and Set to find the duplicate characters in a string. First, we convert the given string to char array. We then create one HashMap with Character as a key and it’s number of occurrences as a value. Then we extract a Set containing all keys of this HashMap using keySet() method. Then we use this keySet to get the duplicate characters i.e characters which have appeared more than once in the given string.
import java.util.HashMap;
import java.util.Set;
class DuplicateCharactersInString
{
static void duplicateCharCount(String inputString)
{
//Creating a HashMap containing char as key and it's occurrences as value
HashMap<Character, Integer> charCountMap = new HashMap<Character, Integer>();
//Converting given string to char array
char[] strArray = inputString.toCharArray();
//checking each char of strArray
for (char c : strArray)
{
if(charCountMap.containsKey(c))
{
//If char is present in charCountMap, incrementing it's count by 1
charCountMap.put(c, charCountMap.get(c)+1);
}
else
{
//If char is not present in charCountMap,
//putting this char to charCountMap with 1 as it's value
charCountMap.put(c, 1);
}
}
//Getting a Set containing all keys of charCountMap
Extract maximum numeric value from a given string | Set 1 (General approach)
Given an alphanumeric string, extract maximum numeric value from that string. Alphabets will only be in lower case. One approach to solving the problem is discussed here, other using Regular expressions is given in Set 2
Examples:
Input : 100klh564abc365bg
Output : 564
Maximum numeric value among 100, 564
and 365 is 564.
Input : abchsd0sdhs
Output : 0
// Java program to extract the maximum value
class ExtractMaxNumberInGivenString
{
// Method to extract the maximum value
static int extractMaximum(String str)
{
int num = 0, res = 0;
// Start traversing the given string
for (int i = 0; i<str.length(); i++)
{
// If a numeric value comes, start converting
// it into an integer till there are consecutive
// numeric digits
if (Character.isDigit(str.charAt(i)))
num = num * 10 + (str.charAt(i)-'0');
// Update maximum value
else
{
res = Math.max(res, num);
// Reset the number
num = 0;
}
}
// Return maximum value
return Math.max(res, num);
}
// Driver method
public static void main(String[] args)
{
String str = "100klh564abc365bg";
System.out.println(extractMaximum(str));
}
}
publicclassDemo{static String FindInt(String str){//First we replace all the non-numeric characters with space
str = str.replaceAll("[^\\d]"," ");//Remove all the trailing spaces
str = str.trim();//Replace consecutive white spaces with one white space
str = str.replaceAll(" +"," ");if(str.equals(""))return"-1";return str;}publicstaticvoidmain(String[] args){
String str ="gibberish123gibberish 456";
System.out.print(FindInt(str));}}
To find an integer from a string, we can use this in-built function called isDigit(). But before this, we have to convert the string to a character array. Look at the example
publicclassDemo{
publicstaticvoidmain(String args[]){
String example ="Find the square of 10";char[] ch = example.toCharArray();
StringBuilder strbuild =newStringBuilder();for(char c : ch){if(Character.isDigit(c)){
strbuild.append(c);}}
System.out.println(strbuild);}}
Output:
10
We first use the toCharArray() method to convert the string to an array of characters. The length of the newly allocated array and the previous string is the same.
Syntax:
string.toCharArray()
Then, we can use the isDigit() method on each element in the array to find if the string has any number
Two Strings are said to be anagrams if they have the exact same characters and their frequency. In this problem you are given two strings, and you need to determine the minimum number of characters to be deleted, so that they become anagrams.
Testcase 1:
String str1="rat";
String str2="tars";
in the above strings 's' is extra in str2, so minimum number of characters to be deleted :1
Testcase2:
String str1="cde";
String str2="abc";
in the above strings, we need to delete 'de' from str1 and 'ab' from str2, so minimum number of characters to be deleted :4
Detailed Explanation:
We have two strings of english alphabet which may or may not have the same length. Anagrams are two words with same characters and frequencies. It is not necessary that the order of the characters is same. We have to determine, how many total number of characters must be deleted from these 2 strings, such that they become anagrams.
Let us look at test cases:
Fig: Sample test cases to make anagrams
If you look at the word rat and the word tars, notice that if we delete the last character s from str2, it would become tar. This word has the exact same characters as the word rat. Hence, we can say that by deleting a total of 1 character(s), the words can be made anagrams.
Similarly, in the second test case, if we delete de from str1 and ab from str2, we delete a total of 4 characters. The image below gives a better idea.
Fig: Number of characters you need to remove to make anagrams
Method 1:
You need to take advantage of the fact, that two words would be anagrams iff they have the exact same characters and frequencies. A brute force method to solve this problem is quite straight forward.
Start with the first character in str1. Iterate through the second string and search if the character is present.
If we find this character, mark it as visited. Otherwise, this character becomes a candidate for deletion. Increase the delete count of str1 by 1.
Do this process for each character of str1.
Similarly, now start with each character of str2. Try to find the character in str1.
If found, mark it as visited, else increase the delete count of str2 by 1.
Now count the number of characters we need to delete from both the strings.
Fig: Counting the number of different characters
Method 2 (Efficient Solution):
The above method works perfectly, but you end up wasting a lot of time iterating over both the strings multiple number of times. We need an optimized approach.
One way to approach the problem is by creating a bucket of each character. Counting sort also works on a similar approach. You initialize an array of 26 integers. Each index holds the frequency of a single character.
arr[0] holds frequency of a
arr[1] holds frequency of b
.
.
arr[25] holds frequency of z
We can now take advantage of this.
Iterate through the first string and increment the indexes corresponding to each character.
Next, go over the second string and decrement the indexes corresponding to each character.
The characters that occurred same number of times will have their frequency changed to 0. The extra characters would have some frequency remaining. The sum of all these frequencies will determine how many characters need to be deleted in order to make these 2 strings anagrams.
Code:
intmakingAnagrams(String s1, String s2){
int[] c = newint[26];
s1 = s1.toLowerCase();
s2 = s2.toLowerCase();
for (int i = 0; i < s1.length(); i++) {
c[s1.charAt(i) - 'a']++;
}
for (int i = 0; i < s2.length(); i++) {
c[s2.charAt(i) - 'a']--;
}
int total = 0;
for (int i : c) {
total += Math.abs(i);
}
return total;
}
We have some strings that needs to be super reduced in size. The string consists of english alphabets from a to z, and they can be duplicated at some places. If we see two adjacent characters that are same, they can be eliminated. Following this pattern we have to return a super compressed/reduced string.
Given a string, remove pairs of adjacent characters in each operation. Repeat this process until no more characters can be removed.
Let us look at some sample test cases:
Input: aabcccdd Output: “bc” Explanation: aabcccdd -> bcccdd -> bcdd -> bc (we eliminate two same adjacent characters at each step)
Input: abba Output: “” Explanation: abba -> aa -> ” “ The string eventually becomes empty after getting super reduced
Fig: Visualization of super reduced strings
Method 1:
A brute force solution to the problem is very straight forward. You start to analyze the string from the beginning, and as soon as you see a matching adjacent character, remove both the characters. Start again from the start position and keep on repeating the process.
You will eventually land up with super reduced strings. But the main problem with this approach is that you will waste a lot of time going over the string again and again. We need to find a time efficient way to solve it.
Method 2:
Whenever we want to look back at the previous elements, a stack data structure is a very wise choice.
Fig: Using a stack to reduce
One approach to solve the problem could be:
Start with the first character.
Check the top of stack. If it is same, then pop the stack.
If the top character is different/empty, just push the current character into the stack.
Eventually, when this process runs for the entire string, all the adjacent characters will get removed. You will be left with a reduced string with characters that could not find a matching adjacent character.
Code:
public String superReducedStringUsingStacks(String str){
Stack<Character> characterStack = new Stack<>();
for (int i = 0; i < str.length(); i++) {
char x = str.charAt(i);
if (characterStack.isEmpty())
characterStack.push(x);
elseif (x == characterStack.peek())
characterStack.pop();
else characterStack.push(x);
}
StringBuilder resultBuilder = new StringBuilder();
for (Character character : characterStack)
resultBuilder.append(character);
return resultBuilder.length() == 0 ?
"Empty String" : resultBuilder.toString();
}
Question: Given a string, find the length of the longest substring without repeating characters. Input: “abcabcbb” Output: “abc”
Input: “bbbb” Output: “b”
The longest substring without repeating letters for “abcabcbb” is “abc”, which the length is 3. For “bbbbb” the longest substring is “b”, with the length of 1.
We definitely have the brute-force method, where we find each string and then compare. But we want to speed up the process.
How can we can look up if a character had existed in the substring instantaneously? The answer is using a simple table to store the characters that have appeared. As you traverse through the string, update by using its ASCII value as index to the table.
The next question is to ask yourself what happens when you found a repeated character? For example, if the string is “abcdcedf”, what happens when you reach the second appearance of ‘c’?
When you have found a repeated character (let’s say at index j), it means that the current substring (excluding the repeated character of course) is a potential maximum, so update the maximum if necessary. It also means that the repeated character must have appeared before at an index i, where i is less than j.
Since you know that all substrings that start before or at index i would be less than your current maximum, you can safely start to look for the next substring with head which starts exactly at index i+1.
Therefore, you would need two indices to record the head and the tail of the current substring. Since i and j both traverse at most n steps, the worst case would be 2n steps, which the run time complexity must be O(n).
Below is the implementation in C++. Beware of the common mistake of not updating the maximum after the main loop, which is easy to forget.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
intlengthOfLongestSubstring(string s)
{
//Get the length of string
intn = s.length();
inti = 0, j = 0;
intmaxLen = 0;
// Set all characters as not-existing
boolexist[256] = { false};
while(j < n)
{
// Check if the character exists
if(exist[s[j]])
{
maxLen = max(maxLen, j-i);
while(s[i] != s[j])
{
exist[s[i]] = false;
i++;
}
i++;
j++;
}
else
{
exist[s[j]] = true;
j++;
}
}
maxLen = max(maxLen, n-i);
returnmaxLen;
}
=============================================
Longest Common Prefix:
Most of the string based problems either revolve around a prefix or a suffix. A prefix is a character or a sequence of characters that occur in the beginning of a string. In this problem we try to find the longest common prefix in an array of strings. We first explore a naive and straight forward approach and then find an optimal solution using a neat little trick called sorting.
public class LongestCommonPrefix {
public String longestCommonPrefix(String[] strs) {
StringBuilder result = new StringBuilder();
// Sort the array
Arrays.sort(strs);
// Get the first and last strings
char[] first = strs[0].toCharArray();
char[] last = strs[strs.length - 1].toCharArray();
// Start comparing
for (int i = 0; i < first.length; i++) {
if (first[i] != last[i])
break;
result.append(first[i]);
}
return result.toString();
}
}
=
import static org.junit.jupiter.api.Assertions.*;
class LongestCommonPrefixTest {
private final LongestCommonPrefix longestCommonPrefix;
1) Java program to find the frequency of one string in another string.
2) Java program for finding Shortest and Longest Words in a String.
3) Java program to reverse a String without using a direct method.
Below solution is for Question 1:
import java.util.Scanner; public class WordFrequencyCounter { public static void main(String args[]) { Scanner scan = new Scanner(System.in); System.out.println("enter main string"); String s = scan.nextLine(); System.out.println("enter string to be searched"); String f = scan.nextLine(); s = s + " "; int l = s.length(); char a; int c = 0; String s1 = ""; for (int i = 0; i < l; i++) { a = s.charAt(i); if (a != ' ') {
s1 = s1 + a; } else { if (s1.equalsIgnoreCase(f) == true) { c++; } s1 = ""; } } System.out.println("Frequency of the word " + f + " is " + c); } }
Output: Enter main string Sachdeva Japneet enter string to be searched Sachdeva Frequency of the word Sachdeva is 1
2) Java program for finding Shortest and Longest Words in a String.
import java.io.BufferedReader; class FindMinMaxString { public static void main(String args[]) { findMethod("My name is Japneet Sachdeva"); } public static void findMethod(String s) { String str = s + " "; char ch = ' '; int len = str.length(), l = 0; int min = len, max = 0; String shortest_word = "", longest_word = "", word = ""; for (int i = 0; i < len; i++) { ch = str.charAt(i); if (ch != ' ') { word += ch;
} //if ends else { l = word.length(); if (l < min) { min = l; shortest_word = word; } //if ends if (l > max) { max = l; longest_word = word; } word = ""; } } System.out.println("Shortest word = " + shortest_word + " with length " + min); System.out.println("Longest word = " + longest_word + " with length " + max); } }
Output: Shortest word = My with length 2 Longest word = Sachdeva with length 8
3) Java program to reverse a String without using a direct method.
import java.io.BufferedReader; public class ReverseOfString { public static String reverseString(String s) { int l = s.length(); String backward = ""; for (int i = l - 1; i >= 0; i--) { backward = backward + s.charAt(i); } return backward; } public static void main(String args[]) { String backwards = reverseString("Japneet Sachdeva"); System.out.println("Reverse String is " + backwards); } }
No comments:
Post a Comment
Note: Only a member of this blog may post a comment.