Given a string s, find the maximum length of substring that contains only one unique character. String contains only lowercase.
Examples :
Input : s = abbcccb Output : 3 Explanation : substring "ccc" is of length 3 with the character 'c' only. Input : s = zaxb Output : 1 Explanation : "z", "a", "x", "b" all are valid substring with length 1.
Naive Approach :
Take a variable maxLength to keep track maximum length of valid substring. We can run three loops, outermost loop points to the starting character of substring, middle loop points to the end character of substring and innermost loop for checking all characters in substring are same or not if all character are same in current substring then update maxLength if length of current substring is greater than maxLength.
Time Complexity : O(N^3) where N is length of String.
Space Complexity : O(1)
naive approach can be optimized by using only two loops outer loop points to starting character of substring since inner loop start running we make sure that inner loop character equals to outer loop character if equals then update maxLength else break the inner loop.
Implementation :
class Main {
// Function to print Maximum length of Substring that contains only unique character
static void maxLengthSubString(String s)
{
// maxLength used to store maximum length of valid Substring
int maxLength = 1;
for (int i = 0; i < s.length(); i++) {
for (int j = i + 1; j < s.length(); j++) {
// if character of inner loop not equal to outer loop character
// then no need to check further
if (s.charAt(i) != s.charAt(j))
break;
// updating maxLength
maxLength = Math.max(maxLength, j - i + 1);
}
}
System.out.println(maxLength);
}
// Driver program
public static void main(String[] args)
{
String str = "abbcccb";
maxLengthSubString(str);
}
}
Time Complexity : O(N^2) where N is length of string
Space Complexity : O(1)
Efficient Approach :
Take two variable :
-> currLength for length of substring that contains unique character.
-> maxLength for store the maximun length of required substring.
Traverse the string only once while traversing make sure that cuurent character equal to previous character, if yes then increment currLength else reset currLength with 1 and update the maxLength.
Implementation :
class Main {
// Function to print Maximum length of Substring that contains only unique character
static void maxLengthSubString(String s)
{
// maxLength used to store maximum length of valid Substring
int maxLength = 1;
// currLength shows current substring length
int currLength = 1;
for (int i = 1; i < s.length(); i++) {
if (s.charAt(i) == s.charAt(i - 1)) {
// increment currLength
currLength += 1;
}
else {
// reset currLength
currLength = 1;
}
maxLength = Math.max(currLength, maxLength);
}
System.out.println(maxLength);
}
// Driver program
public static void main(String[] args)
{
String str = "abbcccb";
maxLengthSubString(str);
}
}
Time Complexity : O(N) where N is length of string
Space Complexity : O(1)