A very common interview challenge is to determine how often words appear in a given string or set of strings. Here’s a version of this: return a list of duplicate words in a sentence.

A very common interview challenge is to determine how often words appear in a given string or set of strings. Here’s a version of this: return a list of duplicate words in a sentence.

(Problem credits: AlgoDaily Day 97)

For example, given 'The dog is the best', returns ["the"].

Likewise, given 'Happy thanksgiving, I am so full', you would return an empty array. This is because there are no duplicates in the string.

My solution:

public static List<String> findDuplicates(String str){
     Set<String> set = new HashSet<>();
     List<String> res = new ArrayList<>();
     String[] words = str.split("\");
     for(int i = 0;i < words.length;i++)
     {
        if(set.contains(words[i].toLowercase())
          res.add(words[i]);
        else 
          set.add(words[i].toLowercase());
     }
     return res;
}

Time complexity: O(n) –> n = length of the string

Space complexity: O(n) –> String array words

This algorithm could be used for problems where some specific items need to placed next to each other where duplicate items could exist. Or where items need to sorted according to a particular criteria and duplicate may/may not exist.

An example problem could be:

Students are asked to stand in non-decreasing order of heights for an annual photo.

Return the minimum number of students not standing in the right positions.  (This is the number of students that must move in order for all students to be standing in non-decreasing order of height.)

Example 1:

Input: [1,1,4,2,1,3]
Output: 3
Explanation: 
Students with heights 4, 3 and the last 1 are not standing in the right positions.

Note:

1. 1 <= heights.length <= 100
2. 1 <= heights[i] <= 100

My solution using counting sort algorithm:

class Solution {
    public int heightChecker(int[] nums) {
         //counting sort
        int[] heights=new int[101]; //100 possible heights
        
        
        for(int height :nums)
            heights[height]++;
        
        int currheight=0;
        int count=0;
        
        for(int i=0;i<nums.length;i++)
        {
            while(heights[currheight]==0)
                currheight++;
            
            if(nums[i]!=currheight)
                count++;
            
            heights[currheight]--;
        }
        
        return count;

    }
}

Another problem of a similar type:

Given an array with n objects colored red, white or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note: You are not suppose to use the library’s sort function for this problem.

Example:

Input: [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]

class Solution {
    public void sortColors(int[] nums) {
        int[] colors=new int[3]; //0,1,2
        for(int i=0;i<nums.length;i++)
            colors[nums[i]]++;
        
        int currcolor=0;
        int i=0;
        while(i<nums.length)
        {
            if(colors[currcolor]!=0)
            {
                nums[i]=currcolor;
                i++;
                colors[currcolor]--;
            }
            else
            {
                currcolor++;
            }
        }
    }
}

(*Some may be solved better without them!)

Using 2 pointers :

1.Fast pointer which shifts to the next node by two places.

fast = fast.next.next;

2. Slow pointer which shifts to the next node by one place.

slow = slow.next;

Initially both are initialized to the head pointer.Use of these pointers helps solve linked lists problems in O(n) time and O(1) space.

Example: The problem of determining whether a given linked list is a palindrome.

https://leetcode.com/problems/palindrome-linked-list/

The solution that I wrote using this concept takes O(n) time and O(1) space. Though the question as to whether changing the input can be considered as solving the problem in O(1) space has been a topic of discussion. I agree to some of the points in the comments which you can check out below and I do consider it as solving the problem using O(1) space.

https://leetcode.com/problems/palindrome-linked-list/discuss/64493/Reversing-a-list-is-not-considered-%22O(1)-space%22

My solution to the above problem:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) 
    {
        ListNode fast_ptr = head;
        ListNode slow_ptr = head;
        
        while(fast_ptr!= null && fast_ptr.next != null )
        {
            fast_ptr = fast_ptr.next.next;
            slow_ptr = slow_ptr.next;
        }
        
        if(fast_ptr != null) //odd length of linked list
            slow_ptr = slow_ptr.next;
        
        slow_ptr = reverse(slow_ptr);
        fast_ptr = head;
        while(slow_ptr != null)
        {
            if(fast_ptr.val != slow_ptr.val)
                return false;
            
            fast_ptr = fast_ptr.next;
            slow_ptr = slow_ptr.next;
        }
        
        return true;
        
    }
    
    public ListNode reverse(ListNode head)
    {
        ListNode curr = head;
        ListNode ptr = head;
        ListNode prev = null;
        
        while(curr != null)
        {
            ptr = curr.next;
            curr.next = prev;
            prev = curr;
            curr = ptr;
        }
        
        return prev;
    }
}

An important tip while solving problems is to keep checking bits of code. Write a function check if it works and then move to the next bit of the problem. Doing so helps resolve problems on the functional level so it becomes easier to debug the program later.

Other examples of problems that can be solved using slow and fast pointers:

For a string to be a palindrome, it should either have all distinct characters in even numbers ( so as to form pairs ) or it could have all characters in even numbers except for a single character which cannot be paired. If the string contains more than one character that cannot be paired then the string is not a palindrome.

Consider the following examples,

input_string=”carrace”

A possible palindromic permutation of the input string could be – “racecar”.

input_string=”daily”

None of the possible permutations of the input string could be palindromic.

My solution uses a HashMap to count the instances of all characters in the string and then check if all characters can be paired.

public boolean isSubstringPalindrome(String s)
	{
		//check if every character appears twice and if not only one character appears once
		HashMap<Character,Integer> map=new HashMap<Character,Integer>();

		for(char ch: s.toCharArray())
			map.put(ch,map.getOrDefault(ch,0)+1);

		boolean check=false;
		for(int x: map.values())
		{
			if(x%2==1 &&  check)
				return false;

			if(x%2==1)
				check=true;
		}

		return true;
	}

Thanks for joining me!

Good company in a journey makes the way seem shorter. — Izaak Walton