Given a string str, the task is to find the length of the longest sub-string which does not have any pair of consecutive same characters.
Examples:
Input: str = “abcdde”
Output: 4
“abcd” is the longest
Input: str = “ccccdeededff”
Output: 5
“ededf” is the longest
Approach: The following steps can be followed to solve the above problem:
- Initialize cnt and maxi as 1 initially, since this is the minimum answer of the length of the longest answer.
- Iterate in the string from 1 to n – 1 and increment cnt by 1 if str[i] != str[i – 1].
- If str[i] == str[i – 1], then re-initialize cnt as 1 and maxi to max(maxi, cnt).
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
int longestSubstring(string s)
{
int cnt = 1;
int maxi = 1;
int n = s.length();
for ( int i = 1; i < n; i++) {
if (s[i] != s[i - 1])
cnt++;
else {
maxi = max(cnt, maxi);
cnt = 1;
}
}
maxi = max(cnt, maxi);
return maxi;
}
int main()
{
string s = "abcdde" ;
cout << longestSubstring(s);
return 0;
}
|
Java
import java.lang.Math;
class GfG
{
static int longestSubstring(String s)
{
int cnt = 1 , maxi = 1 ;
int n = s.length();
for ( int i = 1 ; i < n; i++)
{
if (s.charAt(i) != s.charAt(i- 1 ))
cnt++;
else
{
maxi = Math.max(cnt, maxi);
cnt = 1 ;
}
}
maxi = Math.max(cnt, maxi);
return maxi;
}
public static void main(String []args)
{
String s = "abcdde" ;
System.out.println(longestSubstring(s));
}
}
|
C#
using System;
class GfG
{
static int longestSubstring( string s)
{
int cnt = 1, maxi = 1;
int n = s.Length;
for ( int i = 1; i < n; i++)
{
if (s[i] != s[i - 1])
cnt++;
else
{
maxi = Math.Max(cnt, maxi);
cnt = 1;
}
}
maxi = Math.Max(cnt, maxi);
return maxi;
}
static void Main()
{
string s = "abcdde" ;
Console.WriteLine(longestSubstring(s));
}
}
|
Python3
def longestSubstring(s) :
cnt = 1 ;
maxi = 1 ;
n = len (s);
for i in range ( 1 , n) :
if (s[i] ! = s[i - 1 ]) :
cnt + = 1 ;
else :
maxi = max (cnt, maxi);
cnt = 1 ;
maxi = max (cnt, maxi);
return maxi;
if __name__ = = "__main__" :
s = "abcdde" ;
print (longestSubstring(s));
|
PHP
<?php
function longestSubstring( $s )
{
$cnt = 1;
$maxi = 1;
$n = strlen ( $s );
for ( $i = 1; $i < $n ; $i ++)
{
if ( $s [ $i ] != $s [ $i - 1])
$cnt ++;
else
{
$maxi = max( $cnt , $maxi );
$cnt = 1;
}
}
$maxi = max( $cnt , $maxi );
return $maxi ;
}
$s = "abcdde" ;
echo longestSubstring( $s );
?>
|
Javascript
<script>
function longestSubstring(s)
{
var cnt = 1, maxi = 1;
var n = s.length;
for (i = 1; i < n; i++)
{
if (s.charAt(i) != s.charAt(i-1))
cnt++;
else
{
maxi = Math.max(cnt, maxi);
cnt = 1;
}
}
maxi = Math.max(cnt, maxi);
return maxi;
}
var s = "abcdde" ;
document.write(longestSubstring(s));
</script>
|
Time Complexity: O(n)
Auxiliary Space: O(1)
Approach 2: Using HashTable:
- Create a hash table to keep track of the most recent occurrence of each character.
- Initialize two pointers, left and right, to the beginning of the string.
- Iterate through the string with the right pointer, updating the hash table and the length of the current substring with each new character encountered.
- If a repeated character is encountered, move the left pointer to the next character after the previously occurring instance of that character and update the hash table and substring length accordingly.
- Keep track of the maximum substring length encountered so far.
- Return the maximum substring length.
Here’s the implementation of this approach in C++:
C++
#include <bits/stdc++.h>
using namespace std;
int longestSubstring(string s) {
unordered_map< char , int > mp;
int left = 0, right = 0, maxLen = 0;
while (right < s.length()) {
char c = s[right];
if (mp.find(c) != mp.end() && mp >= left) {
left = mp + 1;
}
mp = right;
maxLen = max(maxLen, right - left + 1);
right++;
}
return maxLen;
}
int main() {
string s = "abcdde" ;
cout << longestSubstring(s) << endl;
return 0;
}
|
Java
import java.util.*;
public class Main {
public static int longestSubstring(String s) {
Map<Character, Integer> mp = new HashMap<>();
int left = 0 , right = 0 , maxLen = 0 ;
while (right < s.length()) {
char c = s.charAt(right);
if (mp.containsKey(c) && mp.get(c) >= left) {
left = mp.get(c) + 1 ;
}
mp.put(c, right);
maxLen = Math.max(maxLen, right - left + 1 );
right++;
}
return maxLen;
}
public static void main(String[] args) {
String s = "abcdde" ;
System.out.println(longestSubstring(s));
}
}
|
Python3
def longestSubstring(s):
mp = {}
left = 0
maxLen = 0
for right in range ( len (s)):
if s[right] in mp and mp[s[right]] > = left:
left = mp[s[right]] + 1
mp[s[right]] = right
maxLen = max (maxLen, right - left + 1 )
return maxLen
if __name__ = = "__main__" :
s = "abcdde"
maxLen = longestSubstring(s)
print (maxLen)
|
C#
using System;
using System.Collections.Generic;
class Program {
static int LongestSubstring( string s)
{
Dictionary< char , int > mp
= new Dictionary< char , int >();
int left = 0, right = 0, maxLen = 0;
while (right < s.Length) {
char c = s[right];
if (mp.ContainsKey(c) && mp >= left) {
left = mp + 1;
}
mp = right;
maxLen = Math.Max(maxLen, right - left + 1);
right++;
}
return maxLen;
}
static void Main( string [] args)
{
string s = "abcdde" ;
Console.WriteLine(LongestSubstring(s));
}
}
|
Javascript
function longestSubstring(s) {
const mp = {};
let left = 0;
let maxLen = 0;
for (let right = 0; right < s.length; right++) {
if (s[right] in mp && mp[s[right]] >= left) {
left = mp[s[right]] + 1;
}
mp[s[right]] = right;
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
}
const s = "abcdde" ;
const maxLen = longestSubstring(s);
console.log(maxLen);
|
Time Complexity: O(n)
Auxiliary Space: O(min(m, n))
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!