i49.Sort_Letters_by_Case.md

i49 · Sort Letters by Case

Medium

https://www.lintcode.com/problem/49/

Description

Given a string chars which contains only letters. Sort it by lower case first and upper case second.

In different languages, chars will be given in different ways. For example, the string "abc" will be given in following ways:

Java: char[] chars = {'a', 'b', 'c'};
Python：chars = ['a', 'b', 'c']
C++：string chars = "abc";

You need to use an in-place algorithm to solve this problem.

It's NOT necessary to keep the original order of lower-case letters and upper case letters.

Example

Example 1:

Input: chars = "abAcD"

Output: "acbAD"

Explanation:

You can also return "abcAD" or "cbaAD" or other correct answers.

Example 2:

Input: chars = "ABC"

Output: "ABC"

Explanation:

You can also return "CBA" or "BCA" or other correct answers.

Challenge

Do it in one-pass and in-place.

Tags

• Quick Select
• Sort

Related Problems

• 1025 Custom Sort String Medium

sol

• 时间复杂度： O ( n ) ， n 为字符串长度。

左右指针相向移动，合起来只需要遍历一次字符串，故时间复杂度为 O ( n ) 。

• 空间复杂度： O ( 1 ) .

不需要创建其他字符串、列表等中间变量。

python

from typing import (
    List,
)

class Solution:
    """
    @param chars: The letter array you should sort by Case
    @return: nothing
    """
    def sortLetters(self, chars: List[str]):
        if not chars:
            return

        left, right = 0, len(chars) - 1
        while left <= right:
            while left <= right and chars[left] >= 'a' and chars[left] <= 'z':
                left += 1
            while left <= right and chars[right] >= 'A' and chars[right] <= 'Z':
                right -= 1

            if left <= right:
                chars[left], chars[right] = chars[right], chars[left]
                left += 1
                right -= 1
        

sol 2

class Solution:
    """
    @param chars: The letter array you should sort by Case
    @return: nothing
    """
    def sortLetters(self, chars: List[str]):
        if not chars:
            return

        chars.sort(key=lambda c: c.isupper())