Scale Engineer

Maximum Value of a String in an Array

Easy
#2277Time: O(N * K), where N is the number of strings in the array and K is the maximum length of a string. This is because we iterate through each of the N strings, and for each string, we perform a check that, in the worst case, involves iterating through all of its K characters.Space: O(1). The memory usage is constant as we only need a few variables to store the maximum value and the state of the current string. The space required does not scale with the size of the input array.
Data structures
ArrayString

Prompt

The value of an alphanumeric string can be defined as:

  • The numeric representation of the string in base 10, if it comprises of digits only.
  • The length of the string, otherwise.

Given an array strs of alphanumeric strings, return the maximum value of any string in strs.

 

Example 1:

Input: strs = ["alic3","bob","3","4","00000"]
Output: 5
Explanation: 
- "alic3" consists of both letters and digits, so its value is its length, i.e. 5.
- "bob" consists only of letters, so its value is also its length, i.e. 3.
- "3" consists only of digits, so its value is its numeric equivalent, i.e. 3.
- "4" also consists only of digits, so its value is 4.
- "00000" consists only of digits, so its value is 0.
Hence, the maximum value is 5, of "alic3".

Example 2:

Input: strs = ["1","01","001","0001"]
Output: 1
Explanation: 
Each string in the array has value 1. Hence, we return 1.

 

Constraints:

  • 1 <= strs.length <= 100
  • 1 <= strs[i].length <= 9
  • strs[i] consists of only lowercase English letters and digits.

Approaches

1 approach with complexity analysis and trade-offs.

The problem asks for the maximum value among a list of strings, where the value's definition depends on whether the string is purely numeric. A direct and efficient solution is to iterate through the array of strings once. For each string, we determine its value and update a running maximum.

Algorithm

  1. Initialize an integer variable maxValue to 0.
  2. Loop through each string in the input array strs.
  3. For each string, determine if it contains only digits.
    • A simple method is to iterate through its characters. If a non-digit character is found, the string is considered alphanumeric.
  4. If the string contains only digits, its value is its numeric representation, obtained via Integer.parseInt(string).
  5. Otherwise, if the string contains any non-digit characters, its value is its length, string.length().
  6. Compare the calculated value of the current string with maxValue and update maxValue if the current value is greater (maxValue = Math.max(maxValue, currentValue)).
  7. After iterating through all the strings, return maxValue.

Walkthrough

We start by initializing a variable, maxValue, to 0. This variable will keep track of the highest value seen so far. We then loop through each string s in the input array strs.

For each string s, we need to determine if it consists solely of digits. A reliable way to do this is to iterate through its characters. We can use a boolean flag, say isNumeric, initialized to true. As we check each character of s, if we encounter a non-digit, we set isNumeric to false and can immediately break out of this inner loop, as we've confirmed the string is not purely numeric.

After checking the characters of s:

  • If isNumeric is still true, it means the string contains only digits. We calculate its value by converting it to an integer using Integer.parseInt(s).
  • If isNumeric is false, it means the string contains at least one letter. Its value is simply its length, s.length().

We then compare this currentValue with our maxValue and update maxValue if currentValue is larger. After iterating through all the strings in the array, maxValue will hold the maximum value found, which we then return.

Here is a Java implementation demonstrating this logic:

class Solution {    public int maximumValue(String[] strs) {        int maxValue = 0;        for (String s : strs) {            boolean isNumeric = true;            for (char c : s.toCharArray()) {                if (!Character.isDigit(c)) {                    isNumeric = false;                    break;                }            }                        int currentValue;            if (isNumeric) {                currentValue = Integer.parseInt(s);            } else {                currentValue = s.length();            }                        maxValue = Math.max(maxValue, currentValue);        }        return maxValue;    }}

Complexity

Time

O(N * K), where N is the number of strings in the array and K is the maximum length of a string. This is because we iterate through each of the N strings, and for each string, we perform a check that, in the worst case, involves iterating through all of its K characters.

Space

O(1). The memory usage is constant as we only need a few variables to store the maximum value and the state of the current string. The space required does not scale with the size of the input array.

Trade-offs

Pros

  • The approach is optimal in terms of time complexity, as every character of every string must be examined in the worst-case scenario.

  • It is highly space-efficient, using only a constant amount of extra space regardless of the input size.

  • The logic is simple, intuitive, and easy to implement correctly.

Cons

  • For this particular problem, the straightforward approach is also the optimal one, so there are no significant disadvantages.

Solutions

public class Solution {    public int MaximumValue(string[] strs) {        return strs.Max(f);    }    private int f(string s) {        int x = 0;        foreach(var c in s) {            if (c >= 'a') {                return s.Length;            }            x = x * 10 + (c - '0');        }        return x;    }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem