Find first non repeated character in a string in Java.
Given a string, find the first non-repeating character in it.
Lets see sample input and output:
Find first non repeated character in a string in Java.
Given a string, find the first non-repeating character in it.
Lets see sample input and output:
Find length of longest substring without repeating characters in Java
Length of the longest substring without repeating characters in Java.
Given a string, find the length of the longest unique substring.
Lets understand what is the input and the expected output.
How substring method creates memory leak in Java
How substring() method of String class use to create memory leaks before Java 7?
We know memory leak happens when any object is not used by the application and also GC is unable to reclaim memory blocked by that object, in that situation we would have Memory leak problem.
Calling substring method creates scenario as described above which leads to Memory leak.
public class SubstringExample { public static void main(String[] args) { String str1 = "Hello, this is Java"; String str2 = str1.substring(7, 11); System.out.println(str2); } }
Below diagram may give some clarity on how substring() method causes Memory leak.
What happens when we call "str1.substring(7, 11);", Ideally what should happen is, str2 should hold the value "this" but that is not happening and it still points to original string referenced by str1.
Before Java 7, String class uses count, offset and value field for representing any String.
count = length of the String
offset = index from which string needs to be printed
value = holds the actual String
String str1 = "Hello, this is Java";
count = 19offset = 0
value = "Hello, this is Java"
Now when we print str1, it refers string present in value and start printing from index mentioned in offset which is 0 and print 19 characters from that index, which is a complete string.
String str2 = str1.substring(7, 11);
count = 4
offset = 7value = "Hello, this is Java"
Now when we print str2, it refers string present in value and start printing from index mentioned in offset which is 7 and print 4 characters from that index, which is "this".
Note: str2 holds the value string "Hello, this is Java" which is not at all required, instead it should store "this".
Basically, str2 still points to the same string referenced by str1, because of which even str2 needs small portion of the string "this" but big string "Hello, this is Java" will not be garbage collected as str2 is holding it.
In Java 1.7 version, offset and count variable which is used to track position of the string to print are removed from String class to prevent memory leak.
You may also like to see
Given an array of integers. All numbers occur thrice except one number which occurs once. Find the number in O(n) time & constant extra space.
Count number of Bits to be flipped to convert A to B
Count number of Set Bits in Integer.
Check if number is Power of Two.
Find all subsets of a set (Power Set).
Skyline Problem in Java.
Find Minimum length Unsorted Subarray, Sorting which makes the complete array sorted
Count trailing zeros in factorial of a number
When to use SOAP over REST Web Service. Is REST better than SOAP?
Tower Of Hanoi Program in Java.
Check if a string is substring of another.
Check if a string is substring of another (LeetCode 28. Implement strStr())
We will see two approach to check whether string is substring of another.
1. Naive approach:
Iterate through String 1 and for each index, check if there is a match found for other string.
Time complexity: O(str1 * str2)
2. Optimized Approach: Knuth Morris Pratt algorithm(KMP)
Time complexity: O(str1 + str2)
Reverse String in Java.
How to Reverse String in Java.
Reverse String in Java. String can be reversed using Iterative and Recursive approach. We will Reverse a String using Recursion and using loop. For reversing a String we should not use any inbuilt methods.
Input: "Reverse String"
Output: "gnirtS esreveR"
Input: "HELLO"
Output: "OLLEH"
Input: "123 abc"
Output: "cba 321"
Check Number is Palindrome in Java Program
Java Program to Check Number is Palindrome.
Java Program to Check Number is Palindrome. Number is called Palindrome, if the reverse of number is equal to original number. Example: 12321, 545.
In this post, we will see Algorithm to check whether number is palindrome or not.
Java Program to check whether Number is Palindrome or not.
It is very easy to check whether Number is Palindrome or not.
Approach 1:
In this approach,
STEP 1: Reverse the original number.
STEP 2: Check, whether original number and reversed number is same. If Yes, then number is
Palindrome otherwise not
Lets understand above algorithm step by step with below example.
Java Program to Check number is Palindrome or not.
package com.javabypatel.string;
public class PalindromeCheck {
public static void main(String[] args) {
palindromCheck(12321);
}
private static void palindromCheck(int number){
if(number < 0){
System.out.println("Invalid number");
return;
}
int temp = number;
int reverseNumber = 0;
while(number > 0){
int mod = number % 10; //Get last digit of number
reverseNumber = (reverseNumber * 10) + mod; //Append Last digit got to reverseNumber.
number = number/10; //Get the remaining number except last digit.
}
if(temp == reverseNumber){
System.out.println("Number is Palindrome");
}else{
System.out.println("Number is not Palindrome");
}
}
}
Approach 2:
STEP 1: Convert the Number to String by using String.valueOf() method.
STEP 2: Reverse the String.
STEP 3: Compare Reversed String with String we got in STEP 1, if both are same then Number is
Palindrome else not.
package com.javabypatel.string;
public class PalindromeCheck{
public static void main(String args[]){
System.out.println(isPalindrome(12122));
}
public static boolean isPalindrome(int number){
if(number < 0){
System.out.println("Invalid number");
return false;
}
String originalString = String.valueOf(number);
String reversedString = "";
for (int i = originalString.length()-1; i >= 0; i--) {
reversedString += originalString.charAt(i);
}
return originalString.equals(reversedString);
}
}
Approach 3:
In Approach 2, we reverse the whole String and then compared it with original string.
In Approach 3, we will check whether string is palindrome without reversing original string and by comparing the characters of original string from both end that is from front and back together.
STEP: 1
Take 2 variable, pointer1 and pointer2.
pointer1 initialise to index 0 and pointer2 initialise to originalString.length()-1.
STEP 2:
Compare characters at pointer1 and pointer2, if they are not same, then they are not Palindrome and stop. If they are same then increment pointer1, decrement pointer2.
STEP 3: Repeat STEP 2 til pointer1 < pointer2.
package com.javabypatel.string;
public class PalindromeCheck{
public static void main(String args[]){
System.out.println(isPalindrome(1221));
}
public static boolean isPalindrome(int number){
if(number < 0){
System.out.println("Invalid number");
return false;
}
String originalString = String.valueOf(number);
int pointer1 = 0;
int pointer2 = originalString.length()-1;
while(pointer1 < pointer2) {
if(originalString.charAt(pointer1) != originalString.charAt(pointer2)) {
return false;
}
pointer1++;
pointer2--;
}
return true;
}
}
I hope below diagram wil help you understand algorithm in better way.
Approach 4:
In this approach, we compare first and last digit of a number, (example say 12321, so we compare first 1 and last 1).
- If they are not same, return false,
- If they are same, remove first and last digit from the number(remaining number 232 ) and repeat the same steps again for remaining number.
package com.javabypatel.string;
public class PalindromeCheck{
public static void main(String[] args) {
int number = 12321;
boolean result = checkPalindrome(number);
System.out.println(result);
}
private static boolean checkPalindrome(int number) {
int divisor = findDivisor(number);
while (number != 0) {
int lastDigit = number % 10; //for 12321 % 10 -> last 1
int firstDigit = number / divisor; //for 12321 / 10000 -> first 1
if (firstDigit != lastDigit) {
return false;
}
number = number % divisor; //for 12321 % 10000 -> remove first 1 from number = 2321
number = number / 10; //for 2321/10 -> remove last 1 from number = 232
//we remove two numbers from 12321 and new number is 232, so we need to calculate new divisor
//we remove two numbers so two zeros should be removed from divisor, so we can do divisor/100 to get
//new divisor
divisor = divisor / 100;
//repeat the step for 232
}
return true;
}
private static int findDivisor(int number){
int divisor = 1;
// 12321/1 = 12321(it is >= 10), so 12321/10 = 1232, so 12321/100 = 123, so 12321/1000 = 12, so 12321/10000 = 1 end
while (number / divisor >= 10) {
divisor = divisor * 10;
}
return divisor;
}
}
You may also like to see
Check whether String is Palindrome or Not in Java.
Count number of Bits to be flipped to convert A to B
Count number of Set Bits in Integer.
Check if number is Power of Two.
Find all subsets of a set (Power Set).
Skyline Problem in Java.
Find Minimum length Unsorted Subarray, Sorting which makes the complete array sorted
Count trailing zeros in factorial of a number
When to use SOAP over REST Web Service. Is REST better than SOAP?
Enjoy !!!!
If you find any issue in post or face any error while implementing, Please comment.
Check whether String is Palindrome or Not in Java.
Java Program to Check whether String is Palindrome or Not.
String is called Palindrome, if it is read same from front as well as from back.
In this post, we will see Algorithm to check whether string is palindrome or not.
Check if Number is Palindrome in Java
Java Program to check whether String is Palindrome or not.
It is very easy to check whether String is Palindrome or not.
Approach 1:
Reverse the original string and compare Reversed String with original string.
If reversed string and original string is same then String is Palindrome else not.
package javabypatel;
public class PalindromeCheck {
public static void main(String args[]){
System.out.println(isPalindrome("ABCBA"));
}
public static boolean isPalindrome(String originalString){
if(originalString == null){
return true;
}
String reversedString = "";
for (int i = originalString.length()-1; i >= 0; i--) {
reversedString += originalString.charAt(i);
}
return originalString.equals(reversedString);
}
}
Approach 2:
In this approach, we will check whether String is Palindrome or not by comparing the characters of string from front and back together.STEP: 1
Take 2 variable, pointer1 and pointer2.
pointer1 initialise to index 0 and pointer2 initialise to originalString.length()-1.
STEP 2:
Compare characters at pointer1 and pointer2, if they are not same, then they are not Palindrome and stop.
If they are same then increment pointer1, decrement pointer2.
Repeat STEP 2 til pointer1 < pointer2.
package javabypatel;
public class PalindromeCheck {
public static void main(String args[]){
System.out.println(isPalindrome("ABCBA"));
}
public static boolean isPalindrome(String originalString){
int pointer1 = originalString.length()-1;
int pointer2=0;
while(pointer1 > pointer2) {
if(originalString.charAt(pointer1) != originalString.charAt(pointer2)) {
return false;
}
pointer1--;
pointer2++;
}
return true;
}
}
You may also like to see
Check if Number is Palindrome in Java
Given an array of integers. All numbers occur thrice except one number which occurs once. Find the number in O(n) time & constant extra space.
Count number of Bits to be flipped to convert A to B
Count number of Set Bits in Integer.
Check if number is Power of Two.
Find all subsets of a set (Power Set).
Skyline Problem in Java.
Find Minimum length Unsorted Subarray, Sorting which makes the complete array sorted
Count trailing zeros in factorial of a number
When to use SOAP over REST Web Service. Is REST better than SOAP?
Tower Of Hanoi Program in Java.
Enjoy !!!!
If you find any issue in post or face any error while implementing, Please comment.
How to Reverse Word in Java Program
How to Reverse Word in Java.
Let's see, how to Reverse Words in Java using Iteration and Recursion. We will Reverse a Word using Recursion and using loop. For reversing a word we should not use any inbuilt methods.
Input: "ReverseWord"
Output: "droWesreveR"
Input: "HELLO"
Output: "OLLEH"
Input: "123abc"
Output: "cba321"
Compress a given string in-place and with constant extra space.
Run-length encoding Program. OR
Given an input string, write a function that returns the Run Length Encoded string for the input string. OR
Compress a given string inplace and with constant extra space.
Compress a given string "aacccddd" to "a2c3d3"
Constraint: Inplace compression, no extra space to be used.
Assumption: Output size will not exceed input size.
Example: input:"acc" output: "a1c2" buffer overflow, because output size length is 4 and input size length is 3. Such inputs will not be given.
Lets understand what is the input and the expected output.
Check whether a given string is an interleaving of two other given strings. (String 1 and String 2 contains unique characters)
Check whether a given string is an interleaving of two other given strings.
(Assume there is unique characters in both strings)
Lets understand what is the input and the expected output.
Print all interleavings of given 2 string.
Print all interleaving of given 2 string.
Lets understand what is the input and the expected output.
Check If two strings are Anagrams.
Check 2 strings are anagrams of each other.
What is Anagram?
An anagram is a rearrangement of the letters of one word or phrase to another word or phrase, using all the original letters exactly once.
Example:
1. "evil" and "vile" is anagram of each other
2. "dog" and "ogd" is anagram of each other
3. "burger" and "burgr" is not a anagram of each other
