Longest Substring Without Repeating Characters

If you want to practice data structure and algorithm programs, you can go through Java coding interview questions.

In this tutorial, we will see Find Longest Substring Without Repeating Characters in java.

Problem

We need to find Longest Substring Without Repeating Characters

Solution

Brute force solution

Find all the substring and check the Longest Substring Without Repeating Characters but time complexity will be O(n^3) in this case.

💻 Awesome Tech Resources:
  • Looking for ⚒️ tech jobs? Go to our job portal.
  • Looking for tech events? Go to tech events 🗓️ Calendar.️

Linear time solution

We can solve this problem in linear time by using some extra spaces.

Here is simple algorithm for solving this problem:

  • Create a visited array and initialize it with -1. This array will track current index for the character.
  • Iterate over String and track the previousIndex. previousIndex is nothing but value of index in visited array
  • If current character is not yet repeated(previousIndex = -1) or it is not in current non repeating character String(i – currentLength > previousIndex) then just increase the current index.
  • If current character is present in current non repeating character String  then
    • Update the current length to start from the next character of previousIndex.
  • Update the index of current character in visited array.

Java program to find longest substring without repeating characters

Output:

The input string is TheJavaTutorial
Longest substring without repeating character: vaTutori

That’s all about finding Longest Substring Without Repeating Characters. You can find more java interview programs.

Related Posts

  • Data structures in java
    16 April

    Data Structures in java

    In this post, we will see about various data structures in java. Data structure is a way of storing and organizing data. Data structure provide a way to process and store data efficiently. For example: 💻 Awesome Tech Resources: Looking for ⚒️ tech jobs? Go to our job portal. Looking for tech events? Go to […]

  • 29 November

    Top 100+ Java coding interview questions

    I have been posting data structure and coding interview questions on various topics such as Array, Queue, Stack, Binary tree, LinkedList, String, Number, ArrayList, etc. So I am consolidating a list of java coding interview questions to create an index post. I will keep adding links to this post whenever I will add new java […]

  • 18 April

    Minimum Number of Jumps to reach last Index

    If you want to practice data structure and algorithm programs, you can go through Java coding interview questions. In this post, we will see how to find Minimum Number of Jumps to reach last Index. Problem Given an array A of positive integers possibly zeroes, every index indicating the maximum length of a jump that can […]

  • 20 February

    Inorder Successor in a Binary Search Tree

    If you want to practice data structure and algorithm programs, you can go through Java coding interview questions. In this post, we will see how to find Inorder Successor in a Binary Search Tree. Problem Given a Binary Search Tree and a target node value. Find the Inorder successor of the given node value in the […]

  • 04 February

    LCA of a K-ary Tree in O(Sqrt(height))

    If you want to practice data structure and algorithm programs, you can go through Java coding interview questions. In this post, we will see about how to find Lowest Common Ancestor of a K-ary Tree in O(Sqrt(height)).We have already seen how to find LCA of n-ary tree in O(n) complexity. Problem Given a K-ary tree and […]

  • 03 February

    Largest Rectangular Area in a Histogram

    If you want to practice data structure and algorithm programs, you can go through Java coding interview questions. In this post, we will see about how to find largest rectangular area in a Histogram. Problem Given an Integer representing number of bars in a Histogram and an array of integers representing the height of the bars […]

Leave a Reply

Your email address will not be published. Required fields are marked *

Subscribe to our newletter

Get quality tutorials to your inbox. Subscribe now.