Remove duplicates from String without Collection API

In this post I am placing one of the challenge which I have faced in Interview and even online coding test for one of the company. Remove duplicate characters / words from String without using Collection API? is also a common interview question for most of the interview attendees in Java technology. The question may ask different like find duplicate character count from given string? Here are the few different solutions I am placing, one among them will be suitable for you. If you haven’t find solution for your problem, please write your problem in comments so I will make some solution ready and post for you.

Problem: Find each character how many times repeated in given String without Collection API?

package com.challenges.string;
public class RepeatedCountOfCharacterInStringWithoutCollections {
    public static void main(String[] args) {
 String str = "javaisocean";
 int count = 0;
 if (str != null) {
            System.out.println();
            System.out.println("Each Character repeated in given String is: ");
     for (int i = 0; i < str.length(); i++) {
  char initialChar = str.charAt(i);
  int length = str.length();
  str = str.replaceAll(str.charAt(i) + "", "");
  count = length - str.length();
              System.out.println(initialChar + " repeated at " + count);
  i--;
     }
 }
    }
}

Output:
Each Character repeated in given String is: 
j repeated at 1
a repeated at 3
v repeated at 1
i repeated at 1
s repeated at 1
o repeated at 1
c repeated at 1
e repeated at 1
n repeated at 1

Problem: Remove duplicate character from given String without using Collection API?

package com.challenges.string;
public class RemoveDuplicateCharactersInStringWithoutCollection {
    public static void main(String[] args) {
 String str = "javaisocean";
 int count = 0;
 String finalString = "";
 if (str != null) {
     for (int i = 0; i < str.length(); i++) {
  char initialChar = str.charAt(i);
  int length = str.length();
  str = str.replaceAll(str.charAt(i) + "", "");
  count = length - str.length();
  if (count == 1)
      finalString = finalString + initialChar + "";
  i--;
      }
 System.out.println("Unique Character in String is: " + finalString);
 }
    }
}

Output:
Unique Character in String is: jvisocen

Problem: Find repeated words in given String with repeated count without using Collection API?

package com.challenges.string;
public class FindRepeatedWordsInStringWithoutCollectionAPI {
    public static void main(String[] args) {
 String str = "Subbareddy Nallamachu Nallamachu Subbareddy Java";
 int count = 0;
 if (str != null) {
      System.out.println();
      System.out.println(

                  "Repeated words in given String with repeted count is: ");
             str = str.toLowerCase();
      String[] arStr = str.split(" ");
      for (int i = 0; i < arStr.length; i++) {
  String s = arStr[i];
  int length = str.length();
  str = str.replaceAll(s, "");
  count = length - str.length();  
  if (count > s.length()) {
        int repeatedCount = count/s.length();
               System.out.println(s+ " "+repeatedCount);
  }
     }
  }
    }
}

Output:
Repeated words in given String with repeted count is: 
subbareddy 2
nallamachu 2

Requesting you to place a comment which you have faced challenges. Thanks for vising. Happy Learning… 🙂

Advertisement

Custom LinkedList implementation using Java

LinkedList is one of the most used data structure. We know how to use java.util.LinkedList class in Java. But, most of them are not aware, how it has been implemented it’s methods internally. Please have a look at below program to know how LinkedList will work internally.

Note: This is not exactly equal to the java.util.LinkedList implementation. This is a custom implementation of LinkedList class.

package com.ds.practice.linked;

public class LinkedList<T> {
 Node head;

 static class Node<T> {
  Node next;
  T data;

  public Node(T data) {
   this.data = data;
   next = null;
  }
 }

 public void add(T new_data) {
  addLast(new_data);
 }

 public void addFirst(T new_data) {
  Node new_node = new Node<Object>(new_data);
  new_node.next = head;
  head = new_node;
 }

 public void add(Node prevNode, T new_data) {
  if (prevNode == null) {
   System.out.println("The give previous Node can't be null");
   return;
  }

  Node new_Node = new Node<Object>(new_data);
  new_Node.next = prevNode.next;
  prevNode.next = new_Node;

 }

 public void addLast(T new_data) {
  if (head == null) {
   head = new Node<Object>(new_data);
   return;
  }

  Node new_node = new Node<Object>(new_data);
  new_node.next = null;

  Node last = head;
  while (last.next != null)
   last = last.next;

  last.next = new_node;
  return;
 }

 public void print() {
  if (head == null) {
   System.out.println("LinkedList is empty");
   return;
  }

  Node tempNode = head;
  while (tempNode != null) {
   System.out.println(tempNode.data + "");
   tempNode = tempNode.next;
  }
 }

 @SuppressWarnings("unchecked")
 public T removeFirst() {
  if (head == null)
   return null;

  Node temp = head;
  if (temp.next == null) {
   head = null;
  } else {
   head = temp.next;
  }
  return (T) temp.data;
 }

 @SuppressWarnings("unchecked")
 public T remove(T data) {
  Node temp = head, prev = null;
  if (temp != null && temp.data == data) {
   head = temp.next;
   return (T) temp.data;
  }

  while (temp != null && temp.data != data) {
   prev = temp;
   temp = temp.next;
  }

  if (temp == null)
   return null;

  prev.next = temp.next;
  return (T) temp.data;
 }

 @SuppressWarnings("unchecked")
 public T removeLast() {
  Node temp = head;
  while (temp.next.next != null)
   temp = temp.next;
  T result = (T) temp.next.data;
  temp.next = null;
  return result;
 }

 public int size() {
  Node temp = head;
  int count = 0;
  while (temp != null) {
   count++;
   temp = temp.next;
  }
  return count;

 }

 public boolean search(T data) {
  Node temp = head;

  while (temp != null) {
   if (temp.data == data)
    return true;

   temp = temp.next;
  }

  return false;

 }

 public static void main(String[] args) {
  LinkedList<Integer> inList = new LinkedList<Integer>();
  inList.add(2);
  inList.addFirst(1);
  inList.addLast(4);
  inList.add(inList.head.next, 4);
  inList.print();
  System.out.println();
  System.out.println("Removed from LinkedList: " + inList.remove(25));
  inList.print();
  System.out.println(inList.search(10));
  System.out.println("Size of the LinkedList is: " + inList.size());
  System.out.println("\n");
  LinkedList<String> stList = new LinkedList<String>();
  stList.add("Subba");
  stList.addLast("Reddy");
  stList.addFirst("Nallamachu");
  System.out.println("Removed First element: " + stList.removeFirst());
  System.out.println("Removed Last element: " + stList.removeLast());
  stList.print();
 }

}

First and Second Highest sum from unsorted Array in Java

Finding the highest and second highest sum from unsorted array in Java is one of the frequently asked question in most of the interviews. They can also ask to write only for finding the highest value sum from unsorted array with single iteration. I am not going to explain more of theory, let’s have a look at below programs.

 

Before going into the first and second highest sum, let’s find highest sum. The below source code will help you to find the same.

package com.ds.practice;

public class HighestSum1 {

public static void main(String[] args) {
// Given unsorted array
int[] ar = { 10, 20, 30, 4, 50, 10 };
// Hold highest two values from array
int first = 0, second = 0;
for (int i = 0; i < ar.length; i++) {
// check the value is greater than first
// if yes, assign first to second and hold new value in first
if (ar[i] > first) {
second = first;
first = ar[i];
}
}

System.out.println(first + second);
}
}

The below source code is the another way of finding the highest sum from an unsorted array in java. This way will help you to find second highest sum from given unsorted array in java.

package com.ds.practice;

public class HighestSum {

public static void main(String[] args) {
// Given unsorted array
int[] ar = { 10, 20, 30, 4, 50, 10 };
// Parameters to hold two highest values from array
int first, second;

//if array has only 1 element
if (ar.length < 2) {
System.out.println(ar[0]);
}
//if array has only 2 elements
else if (ar.length < 3) {
System.out.println(ar[0] + ar[1]);
}
//if array has more than 2 elements
else {

// take first 2 elements into first and second
if (ar[0] > ar[1]) {
first = ar[0];
second = ar[1];
} else {
first = ar[1];
second = ar[0];
}

//loop remaining elements in array and change first and second values based on value
for (int i = 2; i < ar.length; i++) {
if (ar[i] > first) {
second = first;
first = ar[i];
} else if (ar[i] > second && ar[i] != first) {
second = ar[i];
}
}

//Printing final highest sum
System.out.println(first + second);
}
}
}

Now, we will enter into the actual problem. The below source will help you how to find highest and second highest sum from given unsorted array in java.

package com.ds.practice;

public class MaxFirstSecondSum {

public static void main(String[] args) {
// Given unsorted array
int[] ar = { 10, 20, 30, 4, 50, 10 };
// Parameters to hold highest 3 values from array
int first = 0, second = 0, third = 0;
// if array has only 1 element
if (ar.length < 2) {
System.out.println(ar[0]);
}
// if array has only 2 elements
else if (ar.length < 3) {
third = ar[0] > ar[1] ? ar[0] : ar[1];
System.out.println(ar[0] + ar[1] + " " + third);
}
// if array has more than 2 elements
else {
// Holding first two elements from array
if (ar[0] > ar[1]) {
first = ar[0];
second = ar[1];
} else {
first = ar[1];
second = ar[0];
}
// Actual logic to find top 3 elements from array
for (int i = 2; i < ar.length; i++) {
if (ar[i] > first) {
third = second;
second = first;
first = ar[i];
} else if (ar[i] > second && ar[i] != first) {
third = second;
second = ar[i];
}
}
System.out.println((first + second) + " " + (second + third));
}
}
}