# LeetCode Judge Route Circle

LeetCode Judge Route Circle
Initially, there is a Robot at position (0, 0). Given a sequence of its moves, judge if this robot makes a circle, which means it moves back to the original place.
The move sequence is represented by a string. And each move is represent by a character. The valid robot moves are `R` (Right), `L` (Left), `U` (Up) and `D` (down). The output should be true or false representing whether the robot makes a circle.
Example 1:

```Input: "UD"
Output: true
```

Example 2:

```Input: "LL"
Output: false```

```class Solution {
public:
bool judgeCircle(string moves) {
int horizon = 0, vertical = 0;
for (auto c : moves) {
if (c == 'U')++vertical;
else if (c == 'D')--vertical;
else if (c == 'L')--horizon;
else if (c == 'R')++horizon;
}
return horizon == 0 && vertical == 0;
}
};
```

# LeetCode Replace Words

LeetCode Replace Words

In English, we have a concept called `root`, which can be followed by some other words to form another longer word - let's call this word `successor`. For example, the root `an`, followed by `other`, which can form another word `another`.
Now, given a dictionary consisting of many roots and a sentence. You need to replace all the `successor` in the sentence with the `root`forming it. If a `successor` has many `roots` can form it, replace it with the root with the shortest length.
You need to output the sentence after the replacement.
Example 1:

```Input: dict = ["cat", "bat", "rat"]
sentence = "the cattle was rattled by the battery"
Output: "the cat was rat by the bat"
```

Note:

1. The input will only have lower-case letters.
2. 1 <= dict words number <= 1000
3. 1 <= sentence words number <= 1000
4. 1 <= root length <= 100
5. 1 <= sentence words length <= 1000

```const int kMaxN = 26;
class Solution {
private:
struct Node {
bool is_word_;
vector<Node*> children_;
Node() :is_word_(false) {
for (int i = 0; i < kMaxN; ++i)
children_.push_back(NULL);
}
};
Node *root_;
void InsertWord(const string& word) {
Node *cur = root_;
for (const auto& c : word) {
int idx = c - 'a';
if (cur->children_[idx] == NULL)cur->children_[idx] = new Node();
cur = cur->children_[idx];
}
cur->is_word_ = true;
}
void ConstructTree(const vector<string>& dict) {
root_ = new Node();
for (const auto& w : dict) {
InsertWord(w);
}
}
string SearchTree(const string& word) {
Node *cur = root_;
string ans = "";
for (const auto& c : word) {
int idx = c - 'a';
if (cur->children_[idx] == NULL)return "";
cur = cur->children_[idx];
ans.push_back(c);
if (cur->is_word_)return ans;
}
return "";
}
public:
string replaceWords(vector<string>& dict, string sentence) {
ConstructTree(dict);
string ans = "";
int i = 0, n = sentence.size();
for (int j = 0; j <= n; ++j) {
if (j == n || sentence[j] == ' ') {
string successor = sentence.substr(i, j - i);
string root = SearchTree(successor);
if (root == "")
ans += successor + " ";
else
ans += root + " ";
i = j + 1;
}
}
return ans.substr(0, ans.size() - 1);
}
};
```

# LeetCode Design Search Autocomplete System

LeetCode Design Search Autocomplete System
Design a search autocomplete system for a search engine. Users may input a sentence (at least one word and end with a special character `'#'`). For each character they type except '#', you need to return the top 3 historical hot sentences that have prefix the same as the part of sentence already typed. Here are the specific rules:

1. The hot degree for a sentence is defined as the number of times a user typed the exactly same sentence before.
2. The returned top 3 hot sentences should be sorted by hot degree (The first is the hottest one). If several sentences have the same degree of hot, you need to use ASCII-code order (smaller one appears first).
3. If less than 3 hot sentences exist, then just return as many as you can.
4. When the input is a special character, it means the sentence ends, and in this case, you need to return an empty list.

Your job is to implement the following functions:
The constructor function:
`AutocompleteSystem(String[] sentences, int[] times):` This is the constructor. The input is historical data`Sentences` is a string array consists of previously typed sentences. `Times` is the corresponding times a sentence has been typed. Your system should record these historical data.
Now, the user wants to input a new sentence. The following function will provide the next character the user types:
`List<String> input(char c):` The input `c` is the next character typed by the user. The character will only be lower-case letters (`'a'` to `'z'`), blank space (`' '`) or a special character (`'#'`). Also, the previously typed sentence should be recorded in your system. The output will be the top 3 historical hot sentences that have prefix the same as the part of sentence already typed.

Example:
Operation: AutocompleteSystem(["i love you", "island","ironman", "i love leetcode"], [5,3,2,2])
The system have already tracked down the following sentences and their corresponding times:
`"i love you"` : `5` times
`"island"` : `3` times
`"ironman"` : `2` times
`"i love leetcode"` : `2` times
Now, the user begins another search:
Operation: input('i')
Output: ["i love you", "island","i love leetcode"]
Explanation:
There are four sentences that have prefix `"i"`. Among them, "ironman" and "i love leetcode" have same hot degree. Since `' '` has ASCII code 32 and `'r'` has ASCII code 114, "i love leetcode" should be in front of "ironman". Also we only need to output top 3 hot sentences, so "ironman" will be ignored.
Operation: input(' ')
Output: ["i love you","i love leetcode"]
Explanation:
There are only two sentences that have prefix `"i "`.
Operation: input('a')
Output: []
Explanation:
There are no sentences that have prefix `"i a"`.
Operation: input('#')
Output: []
Explanation:
The user finished the input, the sentence `"i a"` should be saved as a historical sentence in system. And the following input will be counted as a new search.

Note:

1. The input sentence will always start with a letter and end with '#', and only one blank space will exist between two words.
2. The number of complete sentences that to be searched won't exceed 100. The length of each sentence including those in the historical data won't exceed 100.
3. Please use double-quote instead of single-quote when you write test cases even for a character input.
4. Please remember to RESET your class variables declared in class AutocompleteSystem, as static/class variables are persisted across multiple test cases. Please see herefor more details.

Trie树的应用题。Trie树的节点属性包含is_sentence_以该字符结尾是否是一个句子，cnt_该句子的频率。首先把历史数据插入到Trie树中，记录好相应的is_sentence_和cnt_。

```const int N = 26;
class AutocompleteSystem {
private:
struct Node {
bool is_sentence_;
int cnt_;
vector<Node*> children_;
Node() :is_sentence_(false), cnt_(0){
for (int i = 0; i < N + 1; ++i)children_.push_back(NULL);
}
};
Node *root;
string cur_sentence_;
struct Candidate {
int cnt_;
string sentence_;
Candidate(int &cnt, string &sentence) :cnt_(cnt), sentence_(sentence) {};
bool operator<(const Candidate& cand) const {
return (cnt_ < cand.cnt_) || (cnt_ == cand.cnt_&&sentence_ > cand.sentence_); // caution
}
};
void AddSentence(const string& sentence, const int& time) {
Node *cur = root;
for (const auto& c : sentence) {
int idx = c - 'a';
if (c == ' ')idx = N;
if (cur->children_[idx] == NULL)cur->children_[idx] = new Node();
cur = cur->children_[idx];
}
cur->is_sentence_ = true;
cur->cnt_ += time; // caution
}
void FindSentences(Node *root, string &sentence, priority_queue<Candidate>& candidates) {
if (root != NULL&&root->is_sentence_)candidates.push(Candidate(root->cnt_, sentence));
if (root == NULL)return;
for (int i = 0; i < N + 1; ++i) {
if (root->children_[i] != NULL) {
if (i == N)
sentence.push_back(' ');
else
sentence.push_back('a' + i);
FindSentences(root->children_[i], sentence, candidates);
sentence.pop_back();
}
}
}
void StartWith(priority_queue<Candidate>& candidates) {
Node *cur = root;
for (const auto& c : cur_sentence_) {
int idx = c - 'a';
if (c == ' ')idx = N;
if (cur->children_[idx] == NULL)return;
cur = cur->children_[idx];
}
string sentence = cur_sentence_;
FindSentences(cur, sentence, candidates);
}
public:
AutocompleteSystem(vector<string> sentences, vector<int> times) {
root = new Node(); // caution
cur_sentence_ = ""; // caution
for (int i = 0; i < sentences.size(); ++i)AddSentence(sentences[i], times[i]);
}
vector<string> input(char c) {
if (c == '#') {
cur_sentence_ = ""; // caution
return{};
}
else {
cur_sentence_.push_back(c);
priority_queue<Candidate> candidates;
StartWith(candidates);
if (candidates.empty())return{};
vector<string> ans;
while (!candidates.empty()) {
ans.push_back(candidates.top().sentence_);
candidates.pop();
if (ans.size() == 3)break;
}
return ans;
}
}
};
```

# LeetCode Exclusive Time of Functions

LeetCode Exclusive Time of Functions
Given the running logs of n functions that are executed in a nonpreemptive single threaded CPU, find the exclusive time of these functions.
Each function has a unique id, start from 0 to n-1. A function may be called recursively or by another function.
A log is a string has this format : `function_id:start_or_end:timestamp`. For example, `"0:start:0"` means function 0 starts from the very beginning of time 0. `"0:end:0"` means function 0 ends to the very end of time 0.
Exclusive time of a function is defined as the time spent within this function, the time spent by calling other functions should not be considered as this function's exclusive time. You should return the exclusive time of each function sorted by their function id.
Example 1:

```Input:
n = 2
logs =
["0:start:0",
"1:start:2",
"1:end:5",
"0:end:6"]
Output:[3, 4]
Explanation:
Function 0 starts at time 0, then it executes 2 units of time and reaches the end of time 1.
Now function 0 calls function 1, function 1 starts at time 2, executes 4 units of time and end at time 5.
Function 0 is running again at time 6, and also end at the time 6, thus executes 1 unit of time.
So function 0 totally execute 2 + 1 = 3 units of time, and function 1 totally execute 4 units of time.
```

Note:

1. Input logs will be sorted by timestamp, NOT log id.
2. Your output should be sorted by function id, which means the 0th element of your output corresponds to the exclusive time of function 0.
3. Two functions won't start or end at the same time.
4. Functions could be called recursively, and will always end.
5. 1 <= n <= 100

```class Solution {
private:
struct Node {
int id_;
bool start_;
int timestamp_;
int exclude_time_;
};
void ParseLog(const string& log, Node& node) {
size_t colon_pos = log.find(':');
node.id_ = stoi(log.substr(0, colon_pos));
if (log[colon_pos + 1] == 's')
node.start_ = true;
else
node.start_ = false;
colon_pos = log.find(':', colon_pos + 1);
node.timestamp_ = stoi(log.substr(colon_pos + 1));
node.exclude_time_ = 0;
}
public:
vector<int> exclusiveTime(int n, vector<string>& logs) {
vector<int> ans(n);
stack<Node> stk;
for (const auto& log : logs) {
Node node;
ParseLog(log, node);
if (node.start_) {
stk.push(node);
} else {
Node start_node = stk.top();
stk.pop();
int cur_time = node.timestamp_ - start_node.timestamp_ + 1 - start_node.exclude_time_; // caution
ans[node.id_] += cur_time; // caution
if (!stk.empty())stk.top().exclude_time_ += cur_time + start_node.exclude_time_; // caution
}
}
return ans;
}
};
```

# LeetCode Decode Ways II

LeetCode Decode Ways II
A message containing letters from `A-Z` is being encoded to numbers using the following mapping way:

```'A' -> 1
'B' -> 2
...
'Z' -> 26
```

Beyond that, now the encoded string can also contain the character '*', which can be treated as one of the numbers from 1 to 9.
Given the encoded message containing digits and the character '*', return the total number of ways to decode it.
Also, since the answer may be very large, you should return the output mod 109 + 7.
Example 1:

```Input: "*"
Output: 9
Explanation: The encoded message can be decoded to the string: "A", "B", "C", "D", "E", "F", "G", "H", "I".
```

Example 2:

```Input: "1*"
Output: 9 + 9 = 18
```

Note:

1. The length of the input string will fit in range [1, 105].
2. The input string will only contain the character '*' and digits '0' - '9'.

```const int MOD = 1000000007;
typedef long long ll;
class Solution {
public:
int numDecodings(string s) {
if (s == "" || s[0] == '0')return 0;
s = "^" + s;
int n = s.size();
vector<ll> dp(n, 0);
dp[0] = 1;
if (s[1] == '*')dp[1] = 9;
else dp[1] = 1;
for (int i = 2; i < n; i++)
{
if (s[i] >= '1' && s[i] <= '9')
dp[i] += dp[i - 1] % MOD; // 独自解析
if ((s[i - 1] == '1' && s[i] >= '0' && s[i] <= '9') || (s[i - 1] == '2' && s[i] >= '0' && s[i] <= '6'))
dp[i] += dp[i - 2] % MOD;
if (s[i - 1] == '*'&&s[i] >= '0'&&s[i] <= '9') {
if (s[i] >= '0'&&s[i] <= '6')dp[i] += dp[i - 2] * 2 % MOD;
if (s[i] > '6')dp[i] += dp[i - 2] % MOD;
}
if (s[i] == '*') {
dp[i] += dp[i - 1] * 9 % MOD; // 独自解析
if (s[i - 1] != '*') {
if (s[i - 1] == '1')dp[i] += dp[i - 2] * 9 % MOD;
else if (s[i - 1] == '2')dp[i] += dp[i - 2] * 6 % MOD;
}
else {
dp[i] += dp[i - 2] * 15 % MOD;
}
}
dp[i] %= MOD;
}
return dp[n - 1];
}
};
```

```class Solution {
public:
int numDecodings(string s) {
if (s == "" || s[0] == '0')return 0;
s = "^" + s;
int n = s.size();
vector<ll> dp(n, 0);
dp[0] = 1;
if (s[1] == '*')dp[1] = 9;
else dp[1] = 1;
for (int i = 2; i < n; i++) {
char cur = s[i], pre = s[i - 1];
ll &curCnt = dp[i], preCnt = dp[i - 1], prePreCnt = dp[i - 2];
if (cur == '0') {
if (pre == '1'|| pre == '2')curCnt += prePreCnt % MOD;
else if (pre == '*')curCnt += prePreCnt * 2 % MOD;
else return 0;
}
else if (cur == '*') {
curCnt += preCnt * 9 % MOD;
if (pre == '1')curCnt += prePreCnt * 9 % MOD;
else if (pre == '2')curCnt += prePreCnt * 6 % MOD;
else if (pre == '*')curCnt += prePreCnt * 15 % MOD;
}
else { // ['1','9']
curCnt += preCnt % MOD;
if(pre=='1')curCnt += prePreCnt % MOD;
else if (pre == '2' && cur <= '6')curCnt += prePreCnt % MOD;
else if (pre == '*') {
if (cur <= '6')curCnt += prePreCnt * 2 % MOD;
else curCnt += prePreCnt % MOD;
}
}
curCnt %= MOD;
}
return dp[n - 1];
}
};
```

# LeetCode Solve the Equation

LeetCode Solve the Equation
Solve a given equation and return the value of `x` in the form of string "x=#value". The equation contains only '+', '-' operation, the variable `x`and its coefficient.
If there is no solution for the equation, return "No solution".
If there are infinite solutions for the equation, return "Infinite solutions".
If there is exactly one solution for the equation, we ensure that the value of `x` is an integer.
Example 1:

```Input: "x+5-3+x=6+x-2"
Output: "x=2"
```

Example 2:

```Input: "x=x"
Output: "Infinite solutions"
```

Example 3:

```Input: "2x=x"
Output: "x=0"
```

Example 4:

```Input: "2x+3x-6x=x+2"
Output: "x=-1"
```

Example 5:

```Input: "x=x+2"
Output: "No solution"```

```class Solution {
private:
void convert(string& s, int& a, int& b) {
int aa = 0, bb = 0;
s += "+";
int start = 0, end = 0;
for (end = 0; end < s.size(); ++end) {
if (end != 0 && (s[end] == '+' || s[end] == '-')) { // -x=-1
string tmp = s.substr(start, end - start);
if (tmp.find('x') != string::npos) {
if (tmp == "x" || tmp == "+x")bb += 1;
else if (tmp == "-x")bb -= 1;
else bb += stoi(tmp.substr(0, tmp.size() - 1));
}
else {
aa += stoi(tmp);
}
start = end;
}
}
a = aa;
b = bb;
}
public:
string solveEquation(string equation) {
size_t pos = equation.find('=');
string left = equation.substr(0, pos), right = equation.substr(pos + 1);
int la = 0, lb = 0, ra = 0, rb = 0;
convert(left, la, lb);
convert(right, ra, rb);
int b = lb - rb, a = ra - la;
if (b == 0) {
if (a == 0)return "Infinite solutions";
else return "No solution";
}
else {
return "x=" + to_string(a / b);
}
}
};
```

# LeetCode Design Log Storage System

LeetCode Design Log Storage System
You are given several logs that each log contains a unique id and timestamp. Timestamp is a string that has the following format: `Year:Month:Day:Hour:Minute:Second`, for example, `2017:01:01:23:59:59`. All domains are zero-padded decimal numbers.
Design a log storage system to implement the following functions:
`void Put(int id, string timestamp)`: Given a log's unique id and timestamp, store the log in your storage system.
`int[] Retrieve(String start, String end, String granularity)`: Return the id of logs whose timestamps are within the range from start to end. Start and end all have the same format as timestamp. However, granularity means the time level for consideration. For example, start = "2017:01:01:23:59:59", end = "2017:01:02:23:59:59", granularity = "Day", it means that we need to find the logs within the range from Jan. 1st 2017 to Jan. 2nd 2017.
Example 1:

```put(1, "2017:01:01:23:59:59");
put(2, "2017:01:01:22:59:59");
put(3, "2016:01:01:00:00:00");
retrieve("2016:01:01:01:01:01","2017:01:01:23:00:00","Year"); // return [1,2,3], because you need to return all logs within 2016 and 2017.
retrieve("2016:01:01:01:01:01","2017:01:01:23:00:00","Hour"); // return [1,2], because you need to return all logs start from 2016:01:01:01 to 2017:01:01:23, where log 3 is left outside the range.
```

Note:

1. There will be at most 300 operations of Put or Retrieve.
2. Year ranges from [2000,2017]. Hour ranges from [00,23].
3. Output for Retrieve has no order required.

retrieve的时候，根据粒度，重新设置start和end，比如样例中粒度为Year时，把start改为Year固定，其他时间最小

`"2016:00:00:00:00:00"`

`"2017:12:31:23:59:59"`

```class LogSystem {
private:
struct Node {
int id;
string timestamp;
Node(int i, string t) :id(i), timestamp(t) {};
};
list<Node> log;
string start, end;
public:
LogSystem() {
start = "2000:00:00:00:00:00";
end = "2017:12:31:23:59:59";
}
void put(int id, string timestamp) {
Node node(id, timestamp);
if (log.empty())log.push_back(node);
else {
auto it = log.begin();
while (it != log.end() && (*it).timestamp <= timestamp)++it;
log.insert(it, node);
}
}
vector<int> retrieve(string s, string e, string gra) {
if (gra == "Year") {
s = s.substr(0, 4) + start.substr(4);
e = e.substr(0, 4) + end.substr(4);
}
else if (gra == "Month") {
s = s.substr(0, 7) + start.substr(7);
e = e.substr(0, 7) + end.substr(7);
}
else if (gra == "Day") {
s = s.substr(0, 10) + start.substr(10);
e = e.substr(0, 10) + end.substr(10);
}
else if (gra == "Hour") {
s = s.substr(0, 13) + start.substr(13);
e = e.substr(0, 13) + end.substr(13);
}
else if (gra == "Minute") {
s = s.substr(0, 16) + start.substr(16);
e = e.substr(0, 16) + end.substr(16);
}
vector<int> ans;
auto it = log.begin();
while (it != log.end() && (*it).timestamp < s)++it;
while (it != log.end() && (*it).timestamp <= e) {
ans.push_back((*it).id);
++it;
}
return ans;
}
};
```

Write a function to check whether an input string is a valid IPv4 address or IPv6 address or neither.
IPv4 addresses are canonically represented in dot-decimal notation, which consists of four decimal numbers, each ranging from 0 to 255, separated by dots ("."), e.g.,`172.16.254.1`;
Besides, leading zeros in the IPv4 is invalid. For example, the address `172.16.254.01` is invalid.
IPv6 addresses are represented as eight groups of four hexadecimal digits, each group representing 16 bits. The groups are separated by colons (":"). For example, the address `2001:0db8:85a3:0000:0000:8a2e:0370:7334` is a valid one. Also, we could omit some leading zeros among four hexadecimal digits and some low-case characters in the address to upper-case ones, so `2001:db8:85a3:0:0:8A2E:0370:7334` is also a valid IPv6 address(Omit leading zeros and using upper cases).
However, we don't replace a consecutive group of zero value with a single empty group using two consecutive colons (::) to pursue simplicity. For example, `2001:0db8:85a3::8A2E:0370:7334` is an invalid IPv6 address.
Besides, extra leading zeros in the IPv6 is also invalid. For example, the address `02001:0db8:85a3:0000:0000:8a2e:0370:7334` is invalid.
Note: You may assume there is no extra space or special characters in the input string.
Example 1:

```Input: "172.16.254.1"
Output: "IPv4"
Explanation: This is a valid IPv4 address, return "IPv4".
```

Example 2:

```Input: "2001:0db8:85a3:0:0:8A2E:0370:7334"
Output: "IPv6"
Explanation: This is a valid IPv6 address, return "IPv6".
```

Example 3:

```Input: "256.256.256.256"
Output: "Neither"

1. 只包含数字和点号
2. 包含4个part，每个part用点号分隔
3. 每个part不能有前导0，且数值范围是[0,255]

1. 只包含数字、冒号和a~f或者A~F
2. 包含8个part，每个part用冒号分隔
3. 每个part可以有前导0，但长度不超过4

```class Solution {
private:
bool checkIPv4Part(const string& part) {
size_t len = part.size();
if (len < 1 || len > 3)return false;
if (len > 1 && part[0] == '0')return false;
for (const auto& c : part) {
if (!(c >= '0'&&c <= '9'))return false;
}
int v = stoi(part);
return v >= 0 && v <= 255;
}
bool isIPv4(string& IP) {
IP += ".";
int parts = 0;
size_t start = 0;
while (true) {
size_t pos = IP.find('.', start);
if (pos == string::npos)break;
if (!checkIPv4Part(IP.substr(start, pos - start)))return false;
++parts;
start = pos + 1;
}
return parts == 4;
}
bool checkIPv6Part(const string& part) {
size_t len = part.size();
if (len < 1 || len > 4)return false;
for (const auto& c : part) {
if (!((c >= '0'&&c <= '9') || (c >= 'a'&&c <= 'f') || (c >= 'A'&&c <= 'F')))return false;
}
return true;
}
bool isIPv6(string& IP) {
IP += ":";
int parts = 0;
size_t start = 0;
while (true) {
size_t pos = IP.find(':', start);
if (pos == string::npos)break;
if (!checkIPv6Part(IP.substr(start, pos - start)))return false;
++parts;
start = pos + 1;
}
return parts == 8;
}
public:
if (IP.find('.') != string::npos)
return isIPv4(IP) ? "IPv4" : "Neither";
else return isIPv6(IP) ? "IPv6" : "Neither";
}
};
```

# LeetCode Remove K Digits

LeetCode Remove K Digits
Given a non-negative integer num represented as a string, remove k digits from the number so that the new number is the smallest possible.
Note:

• The length of num is less than 10002 and will be ≥ k.
• The given num does not contain any leading zero.

Example 1:

```Input: num = "1432219", k = 3
Output: "1219"
Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest.
```

Example 2:

```Input: num = "10200", k = 1
Output: "200"
Explanation: Remove the leading 1 and the number is 200. Note that the output must not contain leading zeroes.
```

Example 3:

```Input: num = "10", k = 2
Output: "0"
Explanation: Remove all the digits from the number and it is left with nothing which is 0.```

```class Solution {
public:
string removeKdigits(string num, int k) {
if (k >= num.size())return "0";
string ans = "";
for (const auto& c : num) {
if (ans.empty() || k == 0)ans.push_back(c);
else {
while (!ans.empty() && ans.back() > c) {
ans.pop_back();
if (--k == 0)break;
}
ans.push_back(c);
}
}
while (k-- > 0 && !ans.empty()) ans.pop_back();
while (!ans.empty() && ans[0] == '0')ans.erase(ans.begin());
return ans.empty() ? "0" : ans;
}
};
```

# LeetCode Next Greater Element III

LeetCode Next Greater Element III
Given a positive 32-bit integer n, you need to find the smallest 32-bit integer which has exactly the same digits existing in the integer n and is greater in value than n. If no such positive 32-bit integer exists, you need to return -1.
Example 1:

```Input: 12
Output: 21
```

Example 2:

```Input: 21
Output: -1```

```class Solution {
public:
int nextGreaterElement(int n) {
string s = to_string(n);
int m = s.size();
for (int i = m - 1; i > 0; --i) {
if (s[i] > s[i - 1]) {
int pos = i;
for (int j = i; j < m; ++j) {
if (s[j] > s[i - 1] && s[j] < s[pos]) {
pos = j;
}
}
swap(s[pos], s[i - 1]);
sort(s.begin() + i, s.end());
long long ans = stoll(s);
if (ans <= INT_MAX)return ans;
else return -1;
}
}
return -1;
}
};
```