Java: Find the longest substring without any number and at least one upper case character

Question

Came across a programming exercise and was stuck. The problem is:

You need to define a valid password for an email but the only restrictions are:

The password must contain one uppercase character

The password should not have numeric digit

Now, given a String, find the length of the longest substring which is a valid password. For e.g Input Str = "a0Ba" , the output should be 2 as "Ba" is the valid substring.

I used the concept of longest substring without repeating characters which I already did before but was unable to modify it to find the solution to above problem. My code for longest substring without repeating characters is:

public int lengthOfLongestSubstring(String s) { int n = s.length(); Set<Character> set = new HashSet<>(); int ans = 0, i = 0, j = 0; while (i < n && j < n) { // try to extend the range [i, j] if (!set.contains(s.charAt(j))){ set.add(s.charAt(j++)); ans = Math.max(ans, j - i); } else { set.remove(s.charAt(i++)); } } return ans; }

If you want to do it in an elegant manner, use regex. Search on google about Pattern.matches() and regex. — Justplayit94
– Justplayit94, Commented Sep 8, 2016 at 10:33

Gabriel · Accepted Answer · 2016-09-13 13:46:29Z

How about

final String input = "a0Ba"; final int answer = Arrays.stream(input.split("[0-9]+")) .filter(s -> s.matches("(.+)?[A-Z](.+)?")) .sorted((s1, s2) -> s2.length() - s1.length()) .findFirst() .orElse("") .length(); out.println(answer);

Arrays.stream(input.split("[0-9]+")) splits the original string into an array of strings. The separator is any sequence of numbers (numbers aren't allowed so they serve as separators). Then, a stream is created so I can apply functional operations and transformations.

.filter(s -> s.matches("(.+)?[A-Z](.+)?")) keeps into the stream only strings that have at least one upper-case letter.

.sorted((s1, s2) -> s2.length() - s1.length()) sorts the stream by length (desc).

.findFirst() tries to get the first string of the stream.

.orElse("") returns an empty string if no string was found.

.length(); gets the length of the string.

@Gabriel: yeah my bad. I was suppose to put an empty check to return -1 as the requirement.

hasnae · Accepted Answer · 2016-09-08 10:48:21Z

I suggest that you split your String to have an array of strings without digit:

yourString.split("[0-9]")

Then iterate over this array (says array a) to get the longest string that contains one Upper case character:

a[i].matches("[a-z]*[A-Z]{1}[a-z]*");

Community · Accepted Answer · 2017-05-23 11:54:22Z

You can use a simple array. The algorithm to use would be a dynamic sliding window. Here is an example of a static sliding window: What is a Sliding Window

The algorithm should be as follows:

Keep track of 2 indexes of the array of char. These 2 indexes will be referred to as front and back here, representing the front and back of the array.

Have an int (I'll name it up here) to keep track of the number of upper case char.

Set all to 0.

Use a while loop that terminates if front > N where N is the number of char given.

If the next char is not a number, add 1 to front. Then check if that char is upper case. If so, add 1 to up.

If up is at least 1, update the maximum length if necessary.

If the next char is a number, continue checking the following char if they are also numbers. Set front to the first index where the char is not a number and back to front-1.

Output the maximum length.

Bahadir Tasdemir · Accepted Answer · 2016-09-08 13:29:20Z

You can use my solution which runs in O(n) time and finds the longest part without any digit and with a capital letter:

 String testString = "skjssldfkjsakdfjlskdssfkjslakdfiop7adfaijsldifjasdjfil8klsasdfŞdijpfjapodifjpoaidjfpoaidjpfi9a"; int startIndex = 0; int longestStartIndex = 0; int endIndex = 0; int index = 0; int longestLength = Integer.MIN_VALUE; boolean foundUpperCase = false; while(index <= testString.length()) { if (index == testString.length() || Character.isDigit(testString.charAt(index))) { if (foundUpperCase && index > startIndex && index - startIndex > longestLength) { longestLength = index - startIndex; endIndex = index; longestStartIndex = startIndex; } startIndex = index + 1; foundUpperCase = false; } else if (Character.isUpperCase(testString.charAt(index))) { foundUpperCase = true; } index++; } System.out.println(testString.substring(longestStartIndex, endIndex));

You should maybe check out the Javadoc for java.lang.Character. There are a whole bunch of isSomething methods, e.g. isUpperCase, which is much easier and faster to use than your isCharUpperCase method; and isDigit, which covers a broader range of digits than just 0-9. Plus, if (condition) return true; else return false; is the same as return condition;.
Thank you very much @AndyTurner, that boolean if-else structure is the fault of mine that I do every time, now updated :). I always come across with the character problems every time I build a project so wanted to use a general upper case finder for the letter by using the regex literal which I used before, also you are right about that numbers too, I will update that part, thanks again :) Bu you know, the most important thing here is the algorithm in the iteration ;)

Andy Turner · Accepted Answer · 2016-09-08 11:07:52Z

You don't need regular expressions. Just use a few integers to act as index pointers into the string:

int i = 0; int longestStart = 0; int longestEnd = 0; while (i < s.length()) { // Skip past all the digits. while (i < s.length() && Character.isDigit(s.charAt(i))) { ++i; } // i now points to the start of a substring // or one past the end of the string. int start = i; // Keep a flag to record if there is an uppercase character. boolean hasUppercase = false; // Increment i until you hit another digit or the end of the string. while (i < s.length() && !Character.isDigit(s.charAt(i))) { hasUppercase |= Character.isUpperCase(s.charAt(i)); ++i; } // Check if this is longer than the longest so far. if (hasUppercase && i - start > longestEnd - longestStart) { longestEnd = i; longestStart = start; } } String longest = s.substring(longestStart, longestEnd);

Ideone demo

Whilst more verbose than regular expressions, this has the advantage of not creating any unnecessary objects: the only object created is the longest string, right at the end.

Ankita Mehta · Accepted Answer · 2016-09-08 11:18:17Z

I am using modification of Kadane algorithm to search the required password length. You may use isNumeric() and isCaps() function or include inline if statements. I have shown below with functions.

public boolean isNumeric(char x){ return (x>='0'&&x<='9'); } public boolean isCaps(char x){ return (x>='A'&&x<='Z'); } public int maxValidPassLen(String a) { int max_so_far = 0, max_ending_here = 0; boolean cFlag = false; int max_len = 0; for (int i = 0; i < a.length(); i++) { max_ending_here = max_ending_here + 1; if (isCaps(a.charAt(i))){ cFlag = true; } if (isNumeric(a.charAt(i))){ max_ending_here = 0; cFlag = false; } else if (max_so_far<max_ending_here){ max_so_far = max_ending_here; } if(cFlag&&max_len<max_so_far){ max_len = max_so_far; } } return max_len; }

Hope this helps.

Note: you don't need to cast a char before comparing to int: it is automatically widened. Also, you can use '0' and '9' instead of 48 and 57; it just makes it clear what these magic numbers are. Also if (condition) return true; return false; is the same as return condition;.

sprinter · Accepted Answer · 2016-09-08 11:36:14Z

There are plenty of good answers here but thought it might be of interest to add one that uses Java 8 streams:

IntStream.range(0, s.length()).boxed() .flatMap(b -> IntStream.range(b + 1, s.length()) .mapToObj(e -> s.substring(b, e))) .filter(t -> t.codePoints().noneMatch(Character::isDigit)) .filter(t -> t.codePoints().filter(Character::isUpperCase).count() == 1) .mapToInt(String::length).max();

If you wanted the string (rather than just the length), then the last line can be replaced with:

 .max(Comparator.comparingInt(String::length));

Which returns an Optional<String>.

Ian2thedv · Accepted Answer · 2016-09-08 11:56:47Z

I'd use Streams and Optionals:

public static String getBestPassword(String password) throws Exception { if (password == null) { throw new Exception("Invalid password"); } Optional<String> bestPassword = Stream.of(password.split("[0-9]")) .filter(TypeErasure::containsCapital) .sorted((o1, o2) -> o1.length() > o2.length() ? 1 : 0) .findFirst(); if (bestPassword.isPresent()) { return bestPassword.get(); } else { throw new Exception("No valid password"); } } /** * Returns true if word contains capital */ private static boolean containsCapital(String word) { return word.chars().anyMatch(Character::isUpperCase); }

Be sure to write some unit tests

user2966968 · Accepted Answer · 2016-09-08 14:20:55Z

public String pass(String str){ int length = 0; boolean uppercase = false; String s= ""; String d= ""; for(int i=0;i<str.length();i++){ if(Character.isUpperCase(str.charAt(i)) == true){ uppercase = true; s = s+str.charAt(i); }else if(Character.isDigit(str.charAt(i)) == true ){ if(uppercase == true && s.length()>length){ d = s; s = ""; length = s.length(); uppercase = false; } }else if(i==str.length()-1&&Character.isDigit(str.charAt(i))==false){ s = s + str.charAt(i); if(uppercase == true && s.length()>length){ d = s; s = ""; length = s.length(); uppercase = false; } }else{ s = s+str.charAt(i); } } return d;}

Tekdev · Accepted Answer · 2017-02-05 19:11:02Z

Here is a simple solution with Scala

 def solution(str: String): Int = { val strNoDigit = str.replaceAll("[0-9]", "-") strAlphas = strNoDigit.split("-") Try(strAlphas.filter(_.trim.find(_.isUpper).isDefined).maxBy(_.size)) .toOption .map(_.length) .getOrElse(-1) }

Tekdev · Accepted Answer · 2017-02-05 21:35:34Z

Another solution using tail recursion in Scala

 def solution2(str: String): Int = { val subSt = new ListBuffer[Char] def checker(str: String): Unit = { if (str.nonEmpty) { val s = str.head if (!s.isDigit) { subSt += s } else { subSt += '-' } checker(str.tail) } } checker(str) if (subSt.nonEmpty) { val noDigitStr = subSt.mkString.split("-") Try(noDigitStr.filter(s => s.nonEmpty && s.find(_.isUpper).isDefined).maxBy(_.size)) .toOption .map(_.length) .getOrElse(-1) } else { -1 } }

harry potter · Accepted Answer · 2017-07-05 12:10:32Z

This is a dynamic programming problem. You can solve this yourself using a matrix. It is easy enough. Just give it a try. Take the characters of the password as the rows and columns of the matrix. Add the diagonals if the current character appended to the last character forms a valid password. Start with the smallest valid password as the initial condition.

user1298426 · Accepted Answer · 2017-12-30 11:56:06Z

String[] s = testString.split("[0-9]"); int length = 0; int index = -1; for(int i=0; i< s.length; i++){ if(s[i].matches("[a-z]*.*[A-Z].*[a-z]*")){ if(length <= s[i].length()){ length = s[i].length(); index = i; } } } if(index >= 0){ System.out.println(s[index]); }

user9679929 · Accepted Answer · 2018-04-21 20:57:48Z

//easiest way to do it:

String str = "a0Ba12hgKil8oPlk"; String[] str1 = str.split("[0-9]+"); List<Integer> in = new ArrayList<Integer>(); for (int i = 0; i < str1.length; i++) { if (str1[i].matches("(.+)?[A-Z](.+)?")) { in.add(str1[i].length()); } else { System.out.println(-1); } } Collections.sort(in); System.out.println("string : " + in.get(in.size() - 1));

oxsha · Accepted Answer · 2018-10-17 00:06:10Z

This is my solution with c#. I tested a range of strings and it gave me the correct value. Used Split. No Regex or Substrings. Let me know if it works; open to improvements and corrections.

public static int validPassword(string str) { List<int> strLength = new List<int>(); if (!(str.All(Char.IsDigit))) { //string str = "a0Bb"; string[] splitStrs = str.Split(new char[] { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' }); //check if each string contains a upper case foreach (string s in splitStrs) { //Console.WriteLine(s); if (s.Any(char.IsUpper) && s.Any(char.IsLower) || s.Any(char.IsUpper)) { strLength.Add(s.Length); } } if (strLength.Count == 0) { return -1; } foreach (int i in strLength) { //Console.WriteLine(i); } return strLength.Max(); } else { return -1; } }

PRIBAN91 · Accepted Answer · 2019-01-05 16:32:07Z

I think this solution takes care of all the possible corner cases. It passed all the test cases in an Online Judge. It is a dynamic sliding window O(n) solution.

public class LongestString { public static void main(String[] args) { // String testString = "AabcdDefghIjKL0"; String testString = "a0bb"; int startIndex = 0, endIndex = 0; int previousUpperCaseIndex = -1; int maxLen = 0; for (; endIndex < testString.length(); endIndex++) { if (Character.isUpperCase(testString.charAt(endIndex))) { if (previousUpperCaseIndex > -1) { maxLen = Math.max(maxLen, endIndex - startIndex); startIndex = previousUpperCaseIndex + 1; } previousUpperCaseIndex = endIndex; } else if (Character.isDigit(testString.charAt(endIndex))) { if (previousUpperCaseIndex > -1) { maxLen = Math.max(maxLen, endIndex - startIndex); } startIndex = endIndex + 1; previousUpperCaseIndex = -1; } } if (previousUpperCaseIndex > -1) maxLen = Math.max(maxLen, endIndex - startIndex); System.out.println(maxLen); }}

@roger_that I solved it for at most 1 uppercase character. I checked the question now. I will modify the code according to that.
Thanks roger_that. I have modified my code. Kindly let me know, if any more test cases fails.

Rahul Vaswani · Accepted Answer · 2019-04-24 10:45:34Z

function ValidatePassword(password){ var doesContainNumber = false; var hasUpperCase = false; for(var i=0;i<password.length;i++){ if(!isNaN(password[i])) doesContainNumber = true; if(password[i] == password[i].toUpperCase()) hasUpperCase = true; } if(!doesContainNumber && hasUpperCase) return true; else return false; } function GetLongestPassword(inputString){ var longestPassword = ""; for(var i=0;i<inputString.length-1;i++) { for (var j=i+1;j<inputString.length;j++) { var substring = inputString.substring(i,j+1); var isValid = ValidatePassword(substring); if(isValid){ if(substring.length > longestPassword.length) { longestPassword = substring; } } } } if(longestPassword == "") { return "No Valid Password found"; } else { return longestPassword; } }

Collectives™ on Stack Overflow

Java: Find the longest substring without any number and at least one upper case character

17 Answers 17

5 Comments

Comments

Comments

2 Comments

2 Comments

1 Comment

Comments

Comments

Comments

Comments

Comments

Comments

Comments

Comments

Comments

2 Comments

Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

17 Answers 17

5 Comments

Comments

Comments

2 Comments

2 Comments

1 Comment

Comments

Comments

Comments

Comments

Comments

Comments

Comments

Comments

Comments

2 Comments

Comments

Linked

Related