JERRY E. SMITH, Circuit Judge:
JohnJay Portillo appeals the dismissal of his claims under common law, Texas statutes, and 42 U.S.C. § 1983. He contends that the court erred by dismissing for res judicata, and he challenges the order to pay costs under Federal Rule of Civil Procedure 41(d). We affirm the dismissal and vacate and remand the fee award.
I.
A.
Portillo was a police officer for Houston Community College (“HCC”). In 2010, he approached several of his supervisors, including Chief of Police Gregory Cunningham, about “serious substantive and procedural deficiencies concerning safety in the operation of the HCC police department.” Portillo alleges that none of his supervisors addressed the issues, so he wrote a letter to the president of HCC. Shortly thereafter, a newspaper published an article that referenced that letter. Although Portillo claims he did not leak any information, he says Cunningham accused him of doing so.
Several weeks later, Portilló and two other officers, Navidad Martinez and Edwin Johnson, responded to a disturbance call at HCC and discovered that Joshua Murray, a student, had engaged in vandalism. The officers ultimately arrested Murray, and Portillo filed an incident report. Murray later complained to HCC’s Board of Trustees that Portillo had profiled him because of his race and had used excessive force. Immediately afterward, Cunningham ordered David Moore to begin an investigation. Portillo claims that the purpose of that investigation was not to review Murray’s complaints about profiling or excessive force but instead was to discover whether Portillo had made false statements in his incident report. Portillo asserts that Moore was biased and unfit to be an investigator.
At the beginning of the investigation, Cunningham placed Portillo on administrative leave and ordered him not to engage in any police work during the leave. Thomas Anderson, from the HCC Human Resources Department, also instructed Por-tillo that he was not permitted to enter any HCC building. Moore’s investigation revealed that Portillo had made false statements in the incident report. That finding was based in large part on statements from Johnson and Martinez; Portillo contends that those statements conflict with those officers’ supplementary reports after Murray’s arrest.
As a result of the investigation, Cunningham fired Portillo. Cunningham also filed a “Separation of License” (“F-5”) report with the Texas Commission on Law Enforcement, asking that Portillo’s separation be labeled as a dishonorable discharge, which the Commission apparently accepted. Around the same time, Moore, at either Cunningham’s or John Dziedzic’s direction, “procured” a criminal prosecution of Portillo by making an affidavit stating that Portillo had made false statements in a government record. Portillo was indicted for various offenses but was ultimately found not guilty.
Portillo then petitioned the State Office of Administrative Hearings to change his F-5 report to reflect an honorable discharge. Portillo claims that he cannot find law-enforcement employment with a dishonorable discharge on his record. The administrative judge ordered that the F-5 be changed. Portillo contends that HCC is violating that order by informing potential employers that he was “terminated and is ineligible for rehire.”
B.
In January 2015, Portillo filed his first action in Texas state court. He raised various claims under common law and Texas statutes, naming Cunningham, Moore, Dzi-edzic, Johnson, Heliodoro Martinez, Navi-dad Martinez, HCC, and several John Does as defendants. A few months later, Portillo nonsuited the case under Texas Rule of Civil Procedure 162.
Several weeks after nonsuiting, Portillo filed a new petition in state court, naming all of the same defendants but adding Anderson and Murray. Portillo raised largely the same claims from his first suit with the addition of constitutional claims: He asserted, under § 1983, that the defendants had violated the First, Fourth, Fifth, and Fourteenth Amendments. In September 2015, the state court dismissed with prejudice all of Portillo’s claims, with the exception .of his § 1983 claims and his claims against Murray, who had not moved for dismissal. Several months later, Portil-lo nonsuited the case.
In March 2016, Portillo brought his third action, this time in federal court. He alleged the same claims from state court, minus a Texas statutory claim. He named all of the same defendants. The defendants moved to dismiss on a number of grounds, including res judicata, qualified immunity, and timeliness. The court dismissed for failure to state a claim. The defendants moved for attorneys’ fees and costs under Federal Rule of Civil Procedure 41(d). The court granted the motion, ordering Portillo to pay $110,000.
II.
“Dismissal of a complaint for failure to state a claim is reviewed de novo.” Gines v. D.R. Horton, Inc., 699 F.3d 812, 816 (5th Cir. 2012). “The res judicata effect of a prior judgment is a question of law that this court reviews de novo.” Test Masters Educ. Servs., Inc. v. Singh, 428 F.3d 559, 571 (5th Cir. 2005).
The parties dispute whether the court dismissed all of the claims as res judicata or merely some of them. Portillo claims the court dismissed everything, including his § 1983 claims, as res judicata. The defendants counter that the court dismissed only the common-law claims as res judicata; they assert that it relied on other reasons to dismiss the § 1983 claims.
Portillo has the better understanding of the record. Though the order of dismissal is nonspecific, stating only that the “case is dismissed with prejudice for failure to state a claim and as rendered,”
the record suggests that res judicata was the basis. At the initial conference, the court began by stating, “This case is dismissed as res judicata.”
Most of the argument centered on that issue, and the court essentially stated its view that Portillo’s claims were precluded. For example, it said,
You have to bring, in one action, all the claims that you could have brought. So if in the first suit you pleaded a whole bunch of legal theories, just full of legal theories, and if you left off the United States Constitution, if you left off interstate conspiracies, they’re gone. You cannot replead them.[
]
At the conference on the defendants’ motion for costs—held after the court entered the order of dismissal—the court reiterated its position: “The problem, Mr. Kallinen, is that when Mr. Portillo brings a case and dismisses a case or has it dismissed, it is not what fíne points he may have pleaded that are affected, it is the essence of the transaction.”
Regardless of the district court’s analysis, “[w]e may affirm for any reason supported by the record, even if not relied on by the district court.”
Because the court could have dismissed all of the claims as res judicata, we do not reach the parties contentions over the other potential grounds supporting dismissal.
The issue is thus whether, as a matter of law, res judicata was a proper basis for dismissal. Portillo presents two reasons why it was not.
First, he asserts that the defendants did not request dismissal of the § 1983 claim as res judicata; he theorizes that this prevents the court from dismissing on that basis. Second, Portillo contends that res judicata cannot bar his § 1983 claims because the state court dismissed them without prejudice. Each of those theories fails.
As Portillo notes, the defendants did not explicitly ask the court to dismiss the § 1983 claims as precluded. Rather, they pointed out that the common-law claims were res judicata, and they raised other grounds, such as qualified immunity, against the § 1983 claims. But Federal Rule of Procedure 54(c) provides that “final judgment should grant the relief to which each party is entitled, even if the party has not demanded that relief in its pleadings.” Portillo acknowledges that rule but asserts that it should not apply because he had insufficient notice of the possibility of res-judicata dismissal.
Rule 54(c) does not permit unrequested relief when it “operate[s] to the prejudice of the opposing party,” such as when “relief is finally sought at a [ ] late[ ] stage of the proceedings.”
“Conversely, there is no prejudice when all of the elements justifying such relief were fully established before the district court.”
Where this court has found relief improper under Rule 54(c), the relief has generally been of a substantially different character from that requested. For example, this court held that injunctive relief was improper where the plaintiff had proceeded through trial seeking only money damages and did not request injunctive relief until after final judgment.
Similarly, this court held that rescission was improper where “the party seeking relief not only failed affirmatively to ask for rescission in his complaint but specifically disavowed any intention of seeking such relief.”
This is not a case in which the court ordered substantially different relief to the surprise of the parties. To the contrary, the court repeatedly questioned Portillo’s lawyer about the preclusive effect of the state-court judgment, and it specifically addressed the § 1983 claims. Not only did Portillo have every reason to expect that the court might dismiss his § 1983 claims as precluded, but he also presented his arguments why the court should not. In sum, there was no prejudice, and Rule 54(c) permitted the court to dismiss all of Portillo’s claims as res judicata.
.“[A] federal court must give state court judgments the same preclusive effect they would have in another court of the same state.”
Under Texas law, res judicata applies if there is “(1) a prior final judgment on the merits by a court of competent jurisdiction; (2) identity of parties or those in privity with them; and (3) a second action based on the same claims that were raised or could have been raised in the first action.” Citizens Ins. Co. of Am. v. Daccach, 217 S.W.3d 430, 449 (Tex. 2007). Applying that test, Portillo’s second state-court action bars his claims.
1.
Regarding whether there was a qualifying final judgment, two orders from the second state action are relevant. First, the Texas court entered an interlocutory order dismissing with prejudice all of Por-tillo’s claims except the § 1983 claims.
Second, it dismissed the entire case because Portillo had invoked his right to nonsuit it.
It is the first order that actually has res judicata effect. A dismissal with prejudice is an adjudication on the merits.
And although the dismissal was initially interlocutory, it became final when the court signed the order of nonsuit, thus disposing of all remaining claims.
So, because the dismissal was a final adjudication on the merits, the first prong of the Texas test for res judicata is satisfied.
2.
As for identity of parties, all of the parties were present in the second state action. There is one procedural wrinkle. After the Texas court entered the interlocutory order of dismissal, Portillo amended his petition and did not assert any claims against HOC in the new petition. As a general rule, “[a]n amended petition [] supersedes all prior petitions and operates to dismiss parties and causes of action to the extent they are omitted from the amended pleading.”
But Portil-lo’s amendment does not interfere with the res judicata effect of the dismissal, which gave specific relief to HCC. When a plaintiff amends his petition to abandon claims against a defendant, an interlocutory judgment in favor of that defendant still has preclusive effect once it becomes final. See Radelow-Gittens Real Prop. Mgmt. v. Pamex Foods, 735 S.W.2d 558, 560 (Tex. App.—Dallas 1987, writ refd n.r.e.). The second prong is satisfied.
3.
Regarding the existence of the same claims, Portillo asserted various common-law claims along with claims under §§ 1983 and 1985.
Under § 1983, he alleged violations of the First, Fourth, Fifth, and Fourteenth Amendments.
He concedes that the common-law claims were actually raised in state court and are thus barred by res judicata, but he contends that the § 1983 claims do not qualify as claims that “could have been raised in the [earlier] action.” Citizens Ins., 217 S.W.3d at 449.
Texas applies the transactional test to determine whether a claim could have been raised. Barr v. Resolution Tr. Corp. ex rel. Sunbelt Fed. Sav., 837 S.W.2d 627, 631 (Tex. 1992). “A subsequent suit will be barred if it arises out of the same subject matter of a previous suit and which through the exercise of diligence, could have been litigated in a prior suit.” Id. There can be little doubt that Portillo’s constitutional claims arise out of the same facts that he litigated in his earlier suit. All of them are premised on the same alleged course of retaliatory conduct. Indeed, he actually raised § 1983 claims in the previous suit. Thus, under the transactional test, his § 1983 claims are barred by the dismissal.
Portillo presents a single argument to defeat application of res judicata. He contends that because he nonsuited his state case before the court had ruled on the merits of his § 1983 claims, those claims were dismissed without prejudice and cannot be precluded. He relies on two cases that explain that where a court adjudicates a claim on the merits, that claim is no longer subject to the plaintiffs right of nonsuit.
So if a plaintiff nonsuits a case, all of the already adjudicated claims are dismissed with prejudice, and all of the unadjudicated claims are dismissed without prejudice. Id.
But Portillo misunderstands the effect of his nonsuit. His mistake is in assuming that “without prejudice” automatically means that he can refile the claim. Texas courts have rejected that position, explaining that “[a] voluntary nonsuit ... may be subject to res judicata.”
In cases like this, where a plaintiff suffers an adverse judgment and nonsuits the case, courts have barred further litigation of nonsuited claims that should have been litigated in the prior case.
In contrast, when the nonsuited claims are unrelated to the adjudicated claims, the nonsuit will not bar further litigation.
That rule makes sense. Otherwise, plaintiffs could use nonsuits to circumvent the res judicata bar by strategically nonsuiting any claims they wish to preserve for later actions. They could thus do precisely what res judicata forbids: serially litigate claims that ought to be decided together. See Barr, 837 S.W.2d at 631 (describing the policy justifications for res judicata).
In sum, because Portillo’s § 1983 claims should have been brought in the second state-court action, the dismissal with prejudice bars those claims from relitigation. Thus, the third prong of the Texas test is satisfied, and res judicata bars all of Por-tillo’s claims.
III.
Portillo asserts that the court erred in awarding the defendants $110,000 in costs and fees. That “Order on Costs” states only that the defendants “take $110,000 from Portillo”; it does not specify the basis for doing so. But the parties seem to agree that the court awarded the costs under Federal Rule of Civil Procedure 41(d). The defendants had filed a motion for costs under that rule, and the court alluded to it repeatedly during conference. The court expressly stated' that the $110,000 represented 90% of the attorneys’ fees the defendants had incurred in the state litigation and that Rule 41(d) permitted such an award.
Portillo contends the court erred because (1) attorneys’ fees are not recoverable as “costs” under Rule 41(d)—at least on this record—-and (2) the defendants’ evidence of fees is insufficient.
The defendants counter that the rule does permit the award of fees and that they presented sufficient evidence. Because each of Portil-lo’s challenges has merit, we vacate the fee award and remand.
Rule 41(d) provides that “[i]f a plaintiff who previously dismissed an action in any court files an action based on or including the same claim against the same defendant, the court ... may order the plaintiff to pay all or part of the costs of that previous action.” The issue is whether attorneys’ fees incurred in the previous action are recoverable as “costs.” There is a circuit split on that issue, and this court has never weighed in.
Circuit courts have taken three general positions on whether Rule 41(d)’s reference to “costs” includes attorneys’ fees. The Sixth Circuit held that fees are never available under Rule 41(d) because “the rule does not explicitly provide for them.” Rogers v. Wal-Mart Stores, Inc., 230 F.3d 868, 874 (6th Cir. 2000). It explained that, “[w]here Congress has intended to provide for an award of attorney fees, it has usually stated as much and not left the courts guessing.” Id. Because “the law generally recognizes a difference between the terms ‘costs’ and ‘attorney fees’[,]” the Sixth Circuit “assume[d] that Congress was aware of the distinction and was careful with its words when it approved Rule 41(d).” Id.
The Eighth and Tenth Circuits have upheld fees under Rule 41(d) but without analyzing the question at any length. The Eighth Circuit merely said that “[w]e are satisfied the district court did not abuse its discretion in awarding defendant-appellee $200 attorney fees.” Evans v. Safeway Stores, Inc., 623 F.2d 121, 122 (8th Cir. 1980) (per curiam).
And the Tenth Circuit stated that “[ujnder the language of Rule 41(d), the decision whether to impose costs and attorney’s fees is within the discretion of the trial court.”
The Seventh and Fourth Circuits hold that fees are available only if the underlying statute defines “costs” to include fees. The Seventh Circuit rejected the idea that fees were available as a matter of course, observing that “[tjhere is no language in the text of Rule 41(d) indicating that Congress intended to alter the ‘American Rule’ as the rule does not refer to attorneys’ fees as an awardable cost.” Esposito v. Piatrowski, 223 F.3d 497, 500 (7th Cir. 2000). The court looked to a Supreme Court decision that considered whether attorneys’ fees were included in Federal Rule of Civil Procedure 68’s reference to “costs.” Id. at 500-01 (discussing Marek v. Chesny, 473 U.S. 1, 105 S.Ct. 3012, 87 L.Ed.2d 1 (1985)). The Supreme Court said that they were, but only if the underlying statute defined fees as costs. Marek, 473 U.S. at 9, 105 S.Ct. 3012. The Seventh Circuit reasoned that the same logic applied to Rule 41(d). Esposito, 223 F.3d at 501. The Fourth Circuit, after considering all of the cases described above, followed the Seventh Circuit. Andrews v. America’s Living Ctrs., LLC, 827 F.3d 306, 309-12 (4th Cir. 2016). “This rule strikes the right balance between upholding the American Rule and furthering the goal of Rule 41(d) to deter forum shopping and vexatious litigation on the part of the plaintiff.” Id. at 311.
We adopt the position of the Seventh and Fourth Circuits. Generally permitting fees stretches the meaning of Rule 41(d) too far.
But categorically forbidding fees makes little sense where the object— “costs”—is defined to include attorneys’ fees. “[T]he federal Rules of Civil Procedure were adopted in 1938” against the backdrop of the American Rule. Marek, 473 U.S. at 8, 105 S.Ct. 3012. “The ‘American Rule’ ... had become subject to certain exceptions by the late 1930’s[,]” including sometimes allowing an “award [of] attorney’s fees as part of costs” when permitted by a federal statute. Id.
Given this backdrop, “the most reasonable inference is that the term ‘costs’ in Rule 68 was intended to refer to all costs awardable under the relevant substantive statute or other authority.” Id. at 9, 105 S.Ct. 3012. We see no reason to treat Rule 41(d) differently: Fee awards are permitted under Rule 41(d) only if the underlying statute defines “costs” to include fees.
The first question is thus whether the underlying statute permits the award of fees. It does, because Portillo brought § 1983 claims in the second state litigation, and § 1988 defines costs in such an action to include fees.
But, attorney fees are available only to a “prevailing party.” See 42 U.S.C. § 1988(b). Thus, the next question is whether, under § 1988, the defendants were the prevailing parties in the second state-court action,
such that they were entitled to fees. Moreover, even if the defendants prevail, the court can award fees “only if the Plaintiffs’ action was frivolous, unreasonable, or without foundation.” Walker v. City of Bogalusa, 168 F.3d 237, 240 (5th Cir. 1999) (quotation marks and citation omitted).
Where a plaintiff has voluntarily dismissed a prior action—which will always be the case if Rule 41(d) is in play
—“a defendant is not a prevailing party within the meaning of § 1988 ... unless the defendant can demonstrate that the plaintiff withdrew to avoid a disfavorable judgment on the merits.” Dean v. Riser, 240 F.3d 505, 511 (5th Cir. 2001). But where, as here, the defendants actually obtained relief on the merits before Portil-lo’s voluntary dismissal, that rule does not apply. See id. at 509 (explaining that the rule applies to dismissals that occur “before there has been any ruling on the merits”).
Moreover, the fact that the relief addressed state-law claims does not preclude a fee award. “[U]nder our precedent attorney’s fees may be awarded even if the § 1983 claim is not decided, provided that 1) the § 1983 claim of constitutional deprivation was substantial; and 2) the successful pendant claims arose out of a common nucleus of operative facts.” Sw. Bell Tel. Co. v. City of El Paso, 346 F.3d 541, 551 (5th Cir. 2003) (quotation marks and citation omitted). A constitutional claim is “substantial” if it supports federal-question jurisdiction, as Portillo’s claims certainly could have. Id. And, as explained above, all of his claims arose out of a common nucleus of operative facts. Thus, the defendants were prevailing parties in the second state litigation for purposes of § 1988.
But there is no indication that Portillo’s claims were “frivolous, unreasonable, or without foundation.” Walker, 168 F.3d at 240. The state court made no such finding in any of the orders in the record, and the bare fact that it dismissed Portil-lo’s claims does not imply that they were frivolous. See Hidden Oaks Ltd. v. City of Austin, 138 F.3d 1036, 1053 (5th Cir. 1998). Because the district court did not make a finding of frivolousness, it could not properly award fees as costs.
C.
Portillo also contends that the defendants provided insufficient evidence to justify the award of fees. Courts must apply a two-step method for determining a reasonable fee award. Combs v. City of Huntington, Tex., 829 F.3d 388, 391 (5th Cir. 2016). First, they calculate the lodestar, “which is equal to the numbers of hours reasonably expended multiplied by the prevailing hourly rate in the community for similar work.” Id. at 392 (quotation marks and citation omitted). “In ealculat-ing the lodestar, the court should exclude all time that is excessive, duplicative, or inadequately documented.” Id. (quotation marks omitted and alteration adopted). Second, the court should consider whether to decrease or enhance the lodestar based on the Johnson factors.
Id. “The court must provide ‘a reasonably specific explanation for all aspects of a fee determination.’ ” Id. (quoting Perdue v. Kenny A. ex rel. Winn, 559 U.S. 542, 558, 130 S.Ct. 1662, 176 L.Ed.2d 494 (2010)).
Portillo does not challenge the court’s mechanical application of the two-step method; instead, he focuses on inadequate documentation. We review fee awards for abuse of discretion. Id. at 391.
“The documentation supporting a factual finding regarding the amount of attorney’s fees must be sufficient for the court to verify that the applicant has met its burden of establishing an entitlement to a specific award.” Gagnon v. United Technisource, Inc., 607 F.3d 1036, 1044 (5th Cir. 2010). Although courts ordinarily expect applicants to provide contemporaneous billing records, the lack of such records is not necessarily fatal to a fee request, “as long as the evidence produced is adequate to determine reasonable hours.” Id. (quotation marks and citation omitted).
Defendants did not produce sufficient evidence. In support of their motion for costs, they provided only an affidavit from Daniel Ramirez, their attorney. The affidavit stated that Ramirez was licensed in Texas, that he had reviewed the records and determined that $125,715.26 represented the amount of fees and costs that the defendants had incurred in the second state litigation, and that those expenses were not useful to the federal case. Ramirez also stated that his hourly rate is $300, that $185 is the hourly rate of the other attorneys who worked on the case, and that, in aggregate, they had expended 595.91 hours. Although he stated that those values were derived from contemporaneous time records, he did not include any documentation.
Although this court has accepted less-than-perfect documentation,
we have found no case that sanctions the minimal showing that the defendants made here. For example, in Von Clark v. Butler, 916 F.2d 255, 259-60 (5th Cir. 1990), we approved a decision to award only 112.5 hours’ worth of time, versus the 291 hours requested, when the plaintiff had submitted only “a memorandum of law, transcripts of the attorneys’ timesheets showing the daily time spent by each attorney, [and several affidavits from attorneys in the area].” Id. This court characterized the timesheets as only “summaries” because they did not reflect all of the contemporaneous hours billed; we described the evidence as “inadequate to meet applicant’s burden of proof.” Id. In Bynum v. American Airlines, Inc., 166 Fed.Appx. 730, 736 (5th Cir. 2006) (per curiam), we described a showing comparable to the one made here. “The only evidence submitted' ... in support of the[] request for fees and expenses as a sanction was the affidavit of an attorney who in conclusory fashion stated that attorneys’ fees and costs incurred in connection with the defense of this matter totaled $27,943.23.” Id. “Without supporting documentation, it is impossible to determine whether the fees and costs were reasonable and, hence, whether the sanction based on the fees and costs was reasonable.” Id.
Thus, the district court abused its discretion in awarding fees based on such inadequate evidence. Because the court did not make a finding of frivolousness and approved an award supported by insufficient evidence, we vacate the fee award and remand for further proceedings as needed.
The judgment of dismissal is AFFIRMED. The order awarding attorney fees is VACATED and REMANDED.